shsh's blog

Worst case constructions for DSU?
By shsh, history, 6 months ago, In English

What sequences of union/find queries will achieve the worst case complexity of a DSU? I'm specifically interested in a DSU with path compression but without union by rank/size, which has worst case complexity $$$\mathcal{O}(m \log n + n)$$$, but constructions for other variations are welcome as well.

A nice proof for the $$$\mathcal{O}(m \log n + n)$$$ bound would also be appreciated.

Tags dsu
  • Vote: I like it
  • +62
  • Vote: I do not like it

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it +77 Vote: I do not like it

A binomial tree represents one of the worst cases for a DSU.

We define the binomial tree $$$T_k$$$ recursively as follows:

  • $$$T_0$$$ consists of a single vertex.
  • For $$$k\ge 1$$$, $$$T_k$$$ can be constructed by taking two copies of $$$T_{k-1}$$$ and making the root of one a child of the root of the other.
Image (Binomial Tree)

It's clear that $$$T_k$$$ has $$$2^k$$$ vertices and a depth of $$$k+1$$$.

Now, consider a DSU whose structure matches $$$T_k$$$. ($$$k=3$$$ in the following example)

If we repeatedly perform a union operation which attaches the binomial tree as a child of a single vertex, then apply a find operation starting from the deepest vertex, we observe that the resulting DSU structure is similar to $$$T_k$$$ (with an additional vertex).

Image (Union and Find)

Each find operation has a time complexity of $$$\Theta(k)=\Theta(\log n)$$$.

→ Reply
  • »
    »
    6 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    Thanks! Do you have a nice proof for why the bound is $$$\mathcal{O}(m \log n + n)$$$? The proof here is pretty nice, but it actually shows an $$$\mathcal{O}((m + n) \log n)$$$ if I'm not mistaken since the sum of potentials initially can be $$$\mathcal{O}(n \log n)$$$.

    EDIT: Nevermind, the linked proof is actually correct since $$$m$$$ is the total number of operations, not just the number of find operations.

    → Reply
»
6 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

its so white and all over the screen!! shsh posted :)

→ Reply