0
$\begingroup$

On wikipedia (https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Proof_of_O(m_log*_n)_time_complexity_of_Union-Find), they prove that the amortized time for any m Find or Union operations on a disjoint-set forest containing n objects is O(m log* n), where log* denotes the iterated logarithm.

The proof is fairly easy to understand until the end (I screenshot it and don't copy paste it because it might change if it actually was wrong but it's currently the same on the link I provided): enter image description here Several things are obscure to me:

  • First, how do we get from nlog*n to mlog*n, this sounds really wrong to me (or are we assuming m >= n?).
  • I get that there are at most log*n buckets and there can't be more than 2n/2^B elements per bucket of size [B, 2^B-1]. If I'm not mistaken there are m find operations that will make increasing-in-rank sequences with only distinct elements (since once we do a find, it gets connected to the root so it won't matter anymore so there are no nodes that appear twice among all those increasing-in-rank sequences). But how do we extract any information from that?

I might be incorrect and misunderstanding something, I'm far from being an expert in Computer Science.

Improve this question
$\endgroup$
4
  • $\begingroup$ Yes, we do assume $m$ is larger than $n$. Given $n$ elements, and if all are subsequently processed, then there has to be $\log n$ union operations and $n$ find operations. $\endgroup$
    – codeR
    Commented Jul 27 at 7:05
  • $\begingroup$ I am a bit confused with the phrase '... no nodes that appear twice...'. The data structure contains only unique copies of each element. $\endgroup$
    – codeR
    Commented Jul 27 at 7:07
  • $\begingroup$ If you want to read more on the proof, probably standard text books do a better job at explaining the concept. $\endgroup$
    – codeR
    Commented Jul 27 at 7:09
  • $\begingroup$ @codeR if we assume m is larger than n , why wouldn't it be valid to say that T3, the number of links traversed when the buckets are the same, is simply at most n (once we use a link, the node becomes linked to the root so we can't ever get in T3 when leaving that particular node) $\endgroup$
    – FluidMechanics Potential Flows
    Commented Jul 30 at 10:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.