1
$\begingroup$

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 !

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.