How to prove the complexity of DSU that merges by size is O(logN)?

Revision en1, by xzyxzy, 2019-09-07 07:58:16

Just like this:

int find(int x)
  if(f[x]==x) return x;
  return find(f[x]);
void merge(int x,int y)
  if(size[x]<size[y]) swap(x,y);

I've knew that the complexity of merging by MAX-depth is $$$O(logN)$$$. But I can't figure out the proof that the complexity of merging by size is $$$O(logN)$$$. Can anyone help?


  Rev. Lang. By When Δ Comment
en1 English xzyxzy 2019-09-07 07:58:16 459 Initial revision (published)