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.
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).
A binomial tree represents one of the worst cases for a DSU.
We define the binomial tree $$$T_k$$$ recursively as follows:
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).
Each find operation has a time complexity of $$$\Theta(k)=\Theta(\log n)$$$.
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.
its so white and all over the screen!! shsh posted :)