### mostafaabdelaal_03's blog

By mostafaabdelaal_03, history, 6 weeks ago,
int n;
vector<int>p, v;
int get(int a){
return p[a] = (a==p[a]) ? a : get(p[a]);
}
void unin(int a, int b){
a = get(a);
b = get(b);
p[a] = b;
}

I implemented  this code when I was solving problems about Dsu in section Edu..now if I used path compression in get function but I donot Consider the samllest set and larget set in union ..can the comlexity reach O(N)

 » 6 weeks ago, # |   +1 The worst case for a single function call can be $O(n)$, but the time complexity per function call is amortized $O(\log n)$, i.e. $q$ function calls will run in $O(q \log n)$ total time.
 » 6 weeks ago, # |   0
 » 6 weeks ago, # | ← Rev. 3 →   0 Please google it, it's $\mathcal{O}(\log{}n)$ as can be read in cp algorithms website the more queries u use it'll be decreased, worst case will always be n but this will happen only once, after that it'll be n/2 then n/4 so for Q queries, you'll have $\mathcal{O}(Q\log{}n)$ (harmonic series)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +13 CP algorithms says: This simple modification of the operation already achieves the time complexity $O(\log n)$ per call on average (here without proof). you can see, cp-algo doesn't proof the time complexity of the path compression-only approach, and its proof is not that easy as you think. btw you can read "Tarjan-van Leeuwen (1984)" paper for complete proof (I also had this question one day and after searching I found this paper).