# Help Needed in understanding time complexity of DSU

**URL:** <https://discuss.codechef.com/t/help-needed-in-understanding-time-complexity-of-dsu/40907>\
**Category:** help\
**Tags:** graphs, disjoint-set-union\
**Created:** [October 12, 2019, 3:00am UTC](https://discuss.codechef.com/t/help-needed-in-understanding-time-complexity-of-dsu/40907 "2019-10-12T03:00:14Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![arpit728](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arpit728/32/4830_2.png) [@arpit728](https://discuss.codechef.com/u/arpit728)\
**Post date:** [October 12, 2019, 3:00am UTC](https://discuss.codechef.com/t/help-needed-in-understanding-time-complexity-of-dsu/40907/1 "2019-10-12T03:00:15Z")

</div>

I have seen lot of DSU solutions for a problem that implements DSU as shown below.

```
class Dsu {
    private int parent[];

    public Dsu(int N) {
        parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (parent[u] != u) return parent[u] = find(parent[u]);
        return parent[u];
    }

    int union(int u, int v) {
        return parent[find(u)] = find(v);
    }
}

```

I am not able to understand how the time complexity of find() and union() operation is O(1).  
Kindly provide explanation with proof that time complexity would be constant, some learning resources on this would be very useful.

---

<div class="post-metadata">

**Author:** ![thecodearrow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/thecodearrow/32/6575_2.png) [@thecodearrow](https://discuss.codechef.com/u/thecodearrow)\
**Post date:** [October 12, 2019, 3:53am UTC](https://discuss.codechef.com/t/help-needed-in-understanding-time-complexity-of-dsu/40907/2 "2019-10-12T03:53:03Z")

</div>

The union operation (the way you’ve done it) doesn’t use union by rank or size. You can improve the union by checking for size or rank of u and v before deciding to point the leader of u to leader of v.

If you do it by union by rank/size and path compression, the amortized time complexity does reduce to O(alpha(n)) where alpha(n) is the Inverse Ackermann function.

You can learn about it by watching the Advanced Union-Find videos by Prof. Tim Roughgarden here =\> [Algorithms - Tim Roughgarden | Stanford Lagunita - YouTube](https://www.youtube.com/playlist?list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa)

He also talks about the Ackermann function.

Proof–\>

> **[Disjoint-set data structure](https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find)**
>
> In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or dif...

---

<div class="post-metadata">

**Author:** ![victor142](https://discuss.codechef.com/user_avatar/discuss.codechef.com/victor142/32/6068_2.png) [@victor142](https://discuss.codechef.com/u/victor142)\
**Post date:** [October 12, 2019, 3:54am UTC](https://discuss.codechef.com/t/help-needed-in-understanding-time-complexity-of-dsu/40907/3 "2019-10-12T03:54:15Z")

</div>

Have you heard of rank by Union and path compression. You can call them optimization over standard technique.

They have an entire play list…