mostafaabdelaal_03's blog

By mostafaabdelaal_03, history, 7 weeks ago, In English
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)
»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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).