Welcome back.
In the previous video, we discussed that the time complexity of the build heap algorithm is O of N,
and in this video let's discuss the proof of this.
So over here I have a perfect binary tree.
Now remember heaps are complete binary trees right now over here in this in the last level we fill the
nodes from left to right.
Now let's say all the nodes are filled, so it will look like this.
So this is how our heap will look.
All right.
Now let's let me separate this into levels.
Now in the last level let's say there are n nodes.
All right.
Now you can notice that in the previous level there will be n by two nodes which is four over here.
Right.
N is equal to eight in this case.
And n by two is equal to four.
Now in the level which is above this there will be n by four nodes which is two.
And over here there will be n by eight nodes which is equal to one in this case.
Now how many levels are there over here.
Now n is the number of nodes in the last level.
If that is the case, if that is n, then we can say that the number of levels will be equal to log
n right which is equal to eight, log eight over here which is equal to three.
So there are three levels over here.
Now this is level zero.
This is level one.
This is level two and this is level three.
All right.
So there will be log n levels which is equal to three.
So let's just keep this aside and this is our base.
Now let's get to look at the time complexity of the build heap algorithm.
Now the time complexity will depend on the maximum number of swaps that we have to do right when we
bubble down.
So we are doing the bubble down operation or the bubble down function is called on all the internal
nodes.
Right.
So again we take time for operations which are swap operations.
So the time will depend on the maximum number of swaps.
Again when we look at big O we are looking at an upper bound.
All right.
So over here in this level in for these N nodes right.
All their children are null.
Right.
So they there will be no swaps.
So this n just to make it to a pattern, I can write this n as n divided by two to the power zero,
because two to the power zero is equal to one, right.
So this is two to the power one and four can be written as n divided by two to the power two, etc..
So let's go ahead.
So in for these n nodes definitely there will be no swaps required right.
We have already discussed that leaf nodes follow the heap property.
So for over here the number of swaps the max number of swaps will be n divided by two to the power zero
into zero, because for all of these, only zero swaps will be required.
All right.
Now what about the next level for the next level?
For these n by two nodes there can be maximum one swap, right.
For example, if you want to swap this you can maximum swap it one time.
So plus n by two to the power one into one.
Now what about these n by four nodes.
For these n by four nodes.
And again I can write this as n divided by two to the power two.
There can be maximum two swaps right.
I could either swap with one of these two.
That's one swap.
And then if I for example if I swap with this one I can again swap with one of these two.
So again the second time.
So a maximum of two swaps can be done for these n by four nodes.
So I write plus n by two to the power two into two maximum two swaps.
Right.
So this goes on till we reach the root node.
Right now there are log n levels right.
So we can say that this goes on up to n divided by two to the power log n into log n right.
So there can be log n swaps in this case.
So over here we have seen log n is equal to three.
So let's look at this root node over here.
How many swaps can be done.
Maximum one two and three.
So maximum three swaps which is equal to log n.
So that's this log n over here.
Now why do I have two to the power log n.
Let's look at the pattern.
So over here we have two to the power zero.
Right.
And then over here we have two to the power one.
And then over here we have two to the power two.
So it's increasing.
And it will go on up to two to the power log n.
And in this case this is n by eight which is n divided by two to the power three.
So this three over here is log n which we have seen over here is three.
So this goes on till two to the power log n.
So n divided by two to the power log n into log n.
So this is the maximum number of swaps that's required.
So time complexity will depend on the maximum number of operations.
All right.
So after having established this let me just clear this space and take this up.
So we have already established that this is the time complexity right now.
Let's try to simplify this.
Now over here.
This is zero into something right.
So this becomes just zero.
So this is zero.
And we are just left with this part over here.
And you can see that there is n over here everywhere in the numerator.
So let me take this n out and simplify it.
So this becomes one by two over here and two by two square.
And the next term will be three by two to the power, three four by two to the power four.
And the last term will be log n divided by two to the power log n.
All right.
Now let me divide the left and right hand side by two.
So I get two by two is equal to.
And then I have n into and I'm dividing by two or multiplying by one by two.
Right.
So each of these powers can be incremented by one.
So I have one over here two over here three over here.
So when I multiply with one by two the right hand side I just increase these by one.
Right.
So I get n into one by two square plus two by this.
Two plus one.
That is three three by two to the power, three plus one which is four, etc..
And the last term will be log n divided by two to the power log n plus one.
All right.
Now let me just clear this.
So we have tea over here and we have tea by two.
Tea by two over here.
Now let me just do t minus t by two.
So we are going to subtract these two.
Now on the left hand side when I subtract these two I get t minus t by two which is t by two itself.
And you can see that on the right hand side I have n over here and I have n over here.
So let me take that out.
Right.
So the left hand side is t by two.
And the right hand side is n into something.
And this something is if you just subtract what is inside the brackets.
So we need to subtract these two.
Now let me just write this one by two over here.
So I have one by two over here.
Now you can see that if I subtract these two terms they have the same denominator which is two to the
power two.
So I can subtract them.
Right.
So I just need to perform the subtraction on the numerator.
And the denominator stays the same.
So two divided by two square minus one divided by two square is equal to two minus one which is one
divided by two square.
Similarly over here for these two terms.
Also I have two cubed as the denominator.
So let's subtract.
So I get three minus two divided by two cubed which is again one divided by two cube.
And you see that there is a pattern.
So this goes on till over here.
Right now I take log n by two to the power log in.
And the second last element over here.
Now if I subtract these two I will get one divided by two to the power log n.
Now again you can think of it in two ways.
Notice that you have two square and you have two square.
And the numerator is one.
You have two cube and you have two cube.
The numerator is one.
So in in the similar manner you take two to the power log n as the denominator.
And the numerator is one.
Now another way is you can compute the previous term over here right.
So that will be log n minus one.
The numerator will be log n minus one.
And the denominator will be two to the power log n right.
So again log n minus log n minus one.
So the numerator will be one.
And the denominator again will be two to the power log n.
And then we just have this one element more right.
So again we are subtracting this minus this.
So there will be a minus over here.
So it's going to be minus this term which is minus log n divided by two to the power log n plus one.
All right.
So let's take this element over here.
So we have this expression over here.
And I'm just clearing the space.
Now let's try to simplify this.
Now if you look at this part over here you can see this is nothing but a geometric progression.
So for a geometric progression sum up to n terms can be calculated using the formula A into one minus
r to the power n by one minus r.
So this is the formula to sum a geometric progression up to the nth term.
So a is the first term.
The second term will be a into r, the next term will be a into r into r right.
You're just multiplying every time with r, and the nth term will be a into r to the power n minus one.
So again this is the nth term right.
Let me just write that over here.
This is the nth term.
Now you have n minus one over here.
Because in the first term, if you if you take this as the nth term, what would be the first term?
The first term will be a into r to the power one minus one, which is equal to a into r to the power
zero which is equal to a.
And that's our first term over here.
So this is the first term.
This is the nth term.
Now if you do a plus r up to a into r to the power n minus one, you can find this sum over here by
doing a into one minus r to the power n by one minus r.
So this is the formula to find sum up to n terms in a geometric progression.
And notice over here you have a geometric progression because you're just always multiplying with one
by two to get the next term.
All right.
So let me just make some space over here.
And let's try to simplify this expression using the formula which we just now saw.
All right.
So over here t by two is equal to n into whatever I get by simplifying this minus this term over here.
So let's write that over here t by two is equal to n into what we get by simplifying the geometric progression
minus log n by two to the power log n plus one.
All right let's hold there over here.
And let's now have a side note and try to find this expression for this geometric progression over here.
Now over here what will be a a will be one by two which is the first term.
Right.
And what is r.
We are always multiplying with one by two.
Right.
So r is equal to one by two.
In this case notice that we are just multiplying always r over here.
So we know A and we know r.
Now let's find r to the power n.
Now the last term is a into r to the power n minus two.
Right.
And a is equal to one by two a is equal to one by two.
So I can say that the last term is one by two into r to the power n minus one.
So one by two into r to the power n minus one n minus one is equal to this one over here, which is
the last term which is one by two to the power log n.
All right.
Now let me just take this one by two to the right hand side so I can say r to the power n minus one
is two divided by two to the power log n.
All right.
Now let me multiply both the sides with one by two.
Right again r over here r is also equal to one by two.
Right.
So I'm not writing it over here.
But you can just say that this is nothing but one by two.
Let me write it over here.
One by two to the power n minus one.
Right.
So if I multiply this with one by two and the right hand side also with one by two, right.
So I get one by two into two divided by two to the power log n.
So these two cancel out.
So let me write that over here.
So I get r is equal to one by two into two to the power one by two into two divided by two to the power
log n.
And these two cancel out.
And therefore I can say r to the power n is nothing but one by two to the power log n.
And again I'm just keeping it like this because we want it over here.
Right now R is nothing but one by two.
You can write it like that as well.
So we have found that r by r to the power n is one by two to the power log n.
Now why did I multiply with one by two.
Because I have a minus one over here.
Right.
So this over here simplifies to one by two to the power n minus one plus one.
And these cancel out.
And I have just n over here.
And this is nothing but r.
All right.
So that was just a side note.
Let me just clear this up.
So we have found out that R to the power n is one by two to the power log n, and we know that A is
equal to one by two and r is equal to one by two.
So let's now substitute this to this formula over here to find sum up to n terms.
So this one over here this will be equal to one by two into one minus one by two to the power log n.
This is r to the power n right divided by one minus r and r is one by two.
So we have found that t by two is equal to this expression over here.
Now let's clear the space and write this up.
So we continue simplifying this.
Now one minus one by two is nothing but one by two itself.
Now we have one by two in the numerator and in the denominator right.
So we can cancel these two.
All right.
So now the denominator is one.
This is already done right.
This is cancelled out.
So now we just have n into one minus one by two to the power log n minus this one over here.
Now let me just have a side note over here.
We know that log eight to the base two is equal to three because two to the power three is equal to
eight.
We have discussed this previously right.
So log eight is what what will be this value.
This is nothing but two to the power.
What is equal to eight.
And we get three.
So log eight is equal to 3 or 2 to the power three is equal to log eight.
Now instead of this three over here let me write this log eight right over here because three is equal
to log eight.
So I can substitute this three with its equivalent value which is log eight.
So I can say two to the power log eight is equal to this eight.
Right.
So I can say two to the power log eight is equal to eight.
Now instead of eight.
If I write n you can see that two to the power log n is nothing but n.
All right.
So this side note was just to prove to you that two to the power log n is equal to n because the base
over here is two itself.
All right.
So two to the power log n is n.
Now let's substitute that over here.
So we have two to the power log n over here.
So instead of this I can write n.
So this simplifies to two by two is equal to n into one minus one by n.
Because this one by two to the power log n is nothing but one by n right.
So this has been simplified to one by n minus log n divided by two to the power log n plus one.
Now let's try to simplify this.
Also two to the power log n plus one can be written as two to the power log n into two.
Right.
So again why is that so quick.
Side note if you have two to the power a into two to the power B, this is nothing but two to the power
A plus B so we are using this property.
So two to the power log n plus one is two to the power one into two to the power log n.
So if you simplify from the right hand side to the left hand side you we can say two to the power one
plus log n right.
All right.
So that was just a side note.
Now we are simplifying two to the power log n plus one as two into two to the power log n.
Now let's write instead of two to the power log n we know that that's equal to n.
So this denominator over here two to the power log n plus one is nothing but two into n right.
So this is nothing but two into n.
Now let's take the let's open the bracket.
And take the n inside.
So n into one gives me n one by n into n is one and n into log n by two.
N is nothing but log n by two.
So this simplifies to this right.
So we have two by two is equal to this.
Now let's take the two to the right hand side.
So we get t is equal to two n minus two minus log n.
All right.
So let's make some space.
We have found the expression for t.
Now over here you can see that two is a constant.
So this can be just removed when we find Big-O now among two n and log n right.
We know that n dominates or two n dominates.
Right.
So again why is that.
So we have seen the uh the time complexity sheet.
Right.
So over here n goes like this.
The number of operations if it's o of n right.
If it's o of log n, it goes very slowly.
Right.
Like this.
So this dominates.
So this also can be removed.
And two is a constant.
So we can say that the time complexity of the build heap algorithm is O of n.