Havel Hakimi complexity Does anyone know what's the complexity of the Havel & Hakimi algorithm ?
If you sort at every step I'm thinking $n^2 log(n)$ but I'm not sure.
Please provide me with some resources / links or answer here. I was unable to find any. The only one I found was not free.
Thanks in advance !
 A: You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$.  Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$.  In total, the algorithm ends up making $\sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = \Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource  I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out.  Say your sequence is already sorted in non-increasing order.  Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one.  You shouldn't need to resort the whole thing.  If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$.  So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $\leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction).  You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
