xzyxzy's blog

How to prove the complexity of DSU that merges by size is O(logN)?
By xzyxzy, history, 5 years ago, In English

Just like this:

int find(int x)
{
  if(f[x]==x) return x;
  return find(f[x]);
}
void merge(int x,int y)
{
  x=find(x);y=find(y);
  if(size[x]<size[y]) swap(x,y);
  f[y]=x;size[x]+=size[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?

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Everytime you merge a smaller component with a bigger component, it's size will at least double, so every node will be merged at most log(n) times before the size of the component it's in becomes n, which means the path between any node and the root is at most log(n)

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have one doubt. Will the complexity will remain NlogN if I will only apply path compression and Not Apply small to large technique ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Yes, but this is much harder to prove. Idea is to reduce our problem from tree to single path with HLD and then do some calculations.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yeah. I have a little intuition that every time we iterate over some path, it's length will reduce by two. So basically each node will be at most iterated for ~ logN times.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Lets say we have a chain of nodes 1-2-...-n, with root=1 If we call find(i) then we will iterate over values j such that 1 <= j <= i. Every node=j will have as root now the node=1. Every node below i will have the same parent. Now if we call find(j) for j less than i, it will take O(1). If we call find(j) with j greater than i it will pass through i and node=i will not have children anymore, because now subtree of j with be connected with root=1. So I think that we iterate every node at most two times.

        Doesn't that mean, that we have O(n) complexity instead O(n logn) ?

        Maybe I am totally wrong, but I was curious if what I was thinking is right.

        → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

xzyxzy Refer small to large technique. DSU is using same.

→ Reply