We now start to estimate the running time of M operations.

First of all note that the union operation

boils down to T(all calls to FInd) operation.

And also to some constant operations.

Namely, when we have two roots that were found by two calls to.

To find that operation,

we need to hank one of them below other one which is a constant operation.

We just need to change one parent.

And also possibly we need to change the rank value.

Okay.

So for this reason when estimating the total running time we will just assume

that we have m calls to find operation.

Paths node that each Find operation traverses some

pass from a note to find the root of the corresponding tree.

So we traverse some number of edges.

So the total run in time of all the defind operations,

of all the calls to defind operation is just the total number of edges traversed.

So this is what is written here, we just need to count the number

of edges from parent a node i through it's paring j,

at traverse you know these codes.

For technical reasons we will split this number into three terms.

In the first term we will account all the edges that

lead from a vertex to the node to the root of the corresponding tree.

So the first term includes all the edges that lead from

a node to another node, which is the root in this case.

The second term include all the remaining edges where we go from i to j.

Such as there log* of rank of

a is strictly smaller than log* of rank of j, okay?

And their remaining term accounts for everything else,

namely for all the edges where we go from i to j such that j is not the root.

And that log*(rank[i]) = log*(rank[j])).

We're going to show separately for each of these terms that it

is upper bounded by big 0 of m multiplied by log star of m.

Let me show this on a small example as usual.

Assumes that we have such a path that we're going to traverse.

A path from the node at the bottom to the root of the corresponding tree.

So the numbers shown here indicate the ranks of the corresponding nodes.

Then these two nodes, these two edges will be accounted in the first term.

Just because these two nodes lead from a node to the root this thread just lead

from a node to the root of the corresponding tree.

Well, this edge for example will be accounted in the last

term because the rank of this node is 17 and

the rank of this node is 21.

And log star of this numbers are equal.

At the same time, here we have 14 the rank 14, and here we have rank 17.

And the log star of these two numbers are different.

For this reason this hatch will be accounted in the second term, okay?

So on the next sequence of slides,

we are going to estimate separately each of these three terms.

And for each of them, we are going to show that it is at most big O of m

multiplied by log* of m.

The first term is easy to estimate.

Recall that in this term we account for all the edges traversed by find operation.

Where we go from node i to its parent j such that j is the root.

Clearly for each call to find the operation

there are at most two side edges, right?

Which means that we have an upper bound big O of m.

In the second term, we need to estimate that a long number of edges traversed

it during all m calls to the find operation.

Such that we go from node i to its parent j such that j is not the root and

also log star of rank of i is strictly less than log star of rank of j.

We're going to prove here that it is upper bounded by big O of

m multiplied by log star of n.