I have the following pictures sorry top half of first photo

I have the following pictures, sorry top half of first photo harder to read, says

\"make the shorter tree a subtree of the other when two trees merge

additional array height[], where

height[x] is the height of node x in the tree

If x is the root (i.e., label) of a tree, height[x] is the height of the tree

Initially, height[x] =1 for all x\"

The find2(x) algorithm is as follows:

find2(x)

r=x

while (set[r] ? r)

r = set[r]

return r

Just wondering about the last photo, I can\'t see how find2() is O(logN) in worst case,

union3(): O(1), Why is nfind2():O(n logN), and why is (N-1)union3:O(N), and Total: O(N + nlogN). Also don\'t see what \"If N and n are of the same order, the time the sequence of operations takes is O(n log n)\"

Disjoint Set Structures -Approach 3 Solution to problem of Approach 2 Make the shorter tree a subtree of the other when two trees merge Additional array height0. where height Jis the height of nodexin the tree Ifx is the root (e..label) of a tree, heightfxjis the height of the tree Initially, heightMxl m 1 for all x find20) ll same find function in Approach 2 union3(a, b) if (height height(b) height al 1 set a else if (heightla] >height set a else

Solution

In worst case find2() is O(logN) because of the comparisions that are made in the form of Bottom-Up approach.

union3() is O(1) here we perform union 3 with 1 directly within a single instance.

(N-1)union3 means we compute total N given strigs i.e O(N).