# What is the intuition behind the $O(n^2)$ SLINK algorithm?

I've been investigating, reading and testing about hierarchical clustering, more specifically the single linkage approach. To which I understand that the naive approach of going through the entire distance matrix created before-hand, obtaining the minimum distance to merge two clusters and then updating said matrix by deleting the corresponding rows and columns of the merged points/clusters to then create a new one that represents said new cluster is what makes the complexity $O(n^3)$.

I found the SLINK algorithm proposed by R. Sibson that claims to lower the complexity to $O(n^2)$ with the use of the following pointer representations of a dendrogram:

$\pi(N) = N \;\;\; \lambda(N)=\infty$
$\pi(i) > i \;\;\; \lambda(\pi(i))>\lambda(i) \;\;\; for\;i<N$

$\lambda(i) = \inf\left \{ h:\exists j > i \;\; with \; (i,j)\in c(h) \right \}$
$\pi(i) = \max\left \{ j:(i,j) \in c(\lambda(i)) \right \}$

Using the pointer representation defined above, the algorithm is derived from the following recursive equations:

For given $n$ we define $\mu_{n}(i)$ recursively on $i$:

$\mu_{n}(i) = \min\left \{ d(i,n+1), \underset{\pi_{n}(j)=i}{\min} \max \left \{ \mu_{n}(j), \lambda_{n}(i) \right \} \right \}$

Thus $\mu_{n}(i)$ is defined for $i = 1, ..., n$ and since

$\mu_{n}(i) \leqslant d(i,n+1)$

and $d$ is a (finite) DC, $\mu_{n}(i)$ is finite for all $i$. We then define $\pi, \lambda$, which we shall prove to be the pointer representation of $C_{n+1}$, that is, $\pi_{n+1}, \lambda_{n+1}$, as follows.

$\pi(n+1) = n + 1$
$\lambda(n+1) = \infty$

$\lambda(i) = \min\left \{ \mu_{n}(i), \lambda_{n}(i) \right \}$ for $i < n + 1$

$\pi(i) = \pi_{n}(i)$ except that if $\mu_{n}(i) \leqslant \lambda_{n}(i)$ or
$\mu_{n}(\pi_{n}(i)) \leqslant \lambda_{n}(i) \: \: then \: \: \pi(i) = n + 1$, again for $i < n + 1$

The problem I face is that even though I feel like I understand the main gist of the algorithm thanks to the implementation done based on the pseudocode, as well as its connection to the mathematical equations, I don't fully understand the reasoning/intuition behind the equations themselves as they're derived above.

I've also found a summary of the article done by Veronika Strnadova-Neeley that takes a slightly different approach from the original SLINK by Sibson, while still being $O(n^2)$ albeit quite a bit slower as the number of data points increase.

I'm looking for an explanation similar to the summary provided by Veronika which is a lot easier to digest but seems different to the original concept from the article by Sibson, I'd appreciate if anybody's got insight on how to understand these mathematical equations that define the algorithm.