Complexity issue

#1

also according to the union operation applied in the video(since it is not union by rank) what will be the worst case complexity of the find operation and the amortised complexity of find operation in this case as now the depth of the tree can be maximum n for n nodes?

#2

complexity of find operation in this case as the depth of the tree can be maximum n for n nodes will be O(n). but you missed a small detail here in get(), we are doing
return p[x] = get(p[x]) and
not just
return get(p[x]),
this little optimization here compresses the path and make the complexity to O(log n) in worst case/ amortised.
because the path n length path that you might have thought of in the place would break and all the nodes will directly point to one parent.
So the complexity will be O(Log n) and not O(n)

#3

if we are doing union as in the video and not by rank then the worst case complexity of find operation is O(n) and amortised time complexity is O(logn).am i right? because if we do not do union by rank then the max depth possible after performing n union operations is O(n),am i right? and also if this is the case then while finding the complexity for the algorithms should i consider worst case time O(n) or amortised time O(log n)?

#4

In the video, we are doing union by path compression, so its time complexity is O(logn) in worst case/amortised. While calculating complexity, consider amortised complexity.

#5

how can it be O(logn) in worst case if we are doing union by path compression only?example–consider we have two rooted trees every time to make union one having one node and other having x nodes so if we are not performing union by rank then we will attach the tree with x nodes to the tree with 1 node and similarly for n nodes the maximum possible depth is O(n).so if we call find operation for the leaf node the complexity will be O(n) right? so how the complexity in worst case is O(logn) for the video approach?

#6

https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-2
Please give this a read, It have explained the thing visually, It will help you gain more conceptual clarity.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.