mostafaabdelaal_03's blog

WHAT IS THE WORST CASE OF (DSU) WHEN I USE PATH COMPRESSION ONLY
By mostafaabdelaal_03, history, 10 months 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)
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 months 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.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://stackoverflow.com/questions/56229760/what-is-the-complexity-of-path-compression-technique-for-disjoint-set-algorithm

→ Reply
»
10 months 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)

→ Reply
  • »
    »
    10 months 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).

    → Reply