Worst case constructions for DSU?

Revision en2, by shsh, 2025-11-12 09:20:45

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shsh 2025-11-12 09:20:45 85
en1 English shsh 2025-11-12 08:58:19 334 Initial revision (published)