### xzyxzy's blog

By xzyxzy, history, 11 months ago, ,

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?

• +20

 » 11 months ago, # | ← Rev. 2 →   +30 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)
•  » » 11 months ago, # ^ |   +19 Thanks!
 » 11 months ago, # |   +5 I have one doubt. Will the complexity will remain NlogN if I will only apply path compression and Not Apply small to large technique ?
•  » » 11 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » 11 months ago, # ^ |   +5 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.
•  » » » » 11 months ago, # ^ |   +8 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.
•  » » » » » 11 months ago, # ^ |   0 Hepic_Antony_Skarlatos Yeah, you are on right track. But that totally depends on the way you compress the path. I prefer to reduce every time it by 2.
 » 11 months ago, # |   +8 xzyxzy Refer small to large technique. DSU is using same.