So on the other hand the maximal number of

comparisons made by our algorithm corresponds to the depths of our tree.

So the depths is defined as the maximal number of edges run away

from the root to the leaf, to some leaf of our tree.

So and this is exactly the maximal possible number of comparisons

which our algorithm makes.

So now we would like to show that d must be large in our case,

must be at least be big O omega of analog n.

And we know already that our tree contains many, many leaves.

Mean n factorial is a function that grows extremely fast.

Okay so, intuitively we would like to show that if a tree has many,

many leaves, then it has a large depth.

And at least intuitively this clear.

If you have a tree of very small depths then it must just a few leaves, right?

But, we know that it has many, many,

many leaves, in fact at least ten factorial leaves.

To formally show this we need the following, we need the following estimate.

The depths of a binary tree is at least a binary algorithm of its number

of leaves or equivalently 2 to the depths is at least its number of leaves.

Well this can be proved formally, but let me just show you this informally.

Let's concede a tree for example of depth 1.

So in this case, d is equal to 1.

And it is clear that the maximal possible number of leaves

in a tree of depth 1 is equal to 2.

So now, let's try to understand what is the maximal possible

number of leaves in a depth of In a tree of depth 2.

For example, this is a tree of depth 2.

This is another tree of depth 2, it has has three leaves.

And this is a tree of depth 2 that has maximal possible number of leaves,

in this case it is 4.

It is 2 to the d indeed.

And intuitively it is clear that to have a tree of depth d that has

maximal possible number of leaves.

We need to take a tree which has a full binary tree of depth d, right?

And this tree has exactly 2 to the d leaves.

So the maximal number of leaves in a tree of depth d is 2 to the d.