Welcome back.
Let's now take a look at the time and space complexity of the approach that we came up with for solving
the Tower of Hanoi problem.
Over here we have the recursion tree.
Notice that the number of print statements is equal to the number of moves required, because again,
that's how we designed it, right?
We always wanted to have a print statement when a move is made.
First let's now think about the space complexity.
The space complexity of this solution is going to be of the order of N because of the space used on
the recursive call stack.
Notice over here that at any point, the maximum number of simultaneous calls on the recursive call
stack is going to be of the order of n, where n is the number of disks.
Over.
Here we call this function with n equal to three, and over here we have n is equal to two.
And over here we have n is equal to one.
So that's why the space complexity of this solution is of the order of n.
When it comes to the time complexity, it's going to be of the order of two to the power n.
Now there are two ways that we can think about this.
First, let's take a look at the intuitive approach.
If there is only one disk, we have seen that we just have to make one move, which is to move that
particular disk from the from road to the two road.
So this is something that we have seen.
Now if there are two disks, notice that we have to do three moves.
And if there are three disks which is the case over here, we have to do seven moves.
That's 1234567.
So if you take a look at this pattern 137 this pattern over here is actually two to the power n minus
one where n is the number of disks.
So if you have one disk so that's two to the power one minus one which is two minus one which is one
move.
If you have two disks that's two to the power two minus one which is four minus one which is three moves.
And for three disks that's two to the power, three minus one which is eight minus one which is seven
moves.
So that's why the number of moves is two to the power n minus one.
And hence the time complexity would be of the order of two to the power n, because again in each call
we are just doing some constant time operations.
So the number of calls that we are making will be of the order of two to the power n.
Now there is one more way that we can think about when we take a look at the time complexity.
We have discussed that to move n disks, we are actually first moving n minus one disks from the from
rod to the auxiliary rod.
Then we are going to move the nth disk from the from rod to the two rod.
And finally we are going to again move n minus one disks from the auxiliary rod to the two rod.
This is what we have discussed right now.
If we take a look at the time complexity of this, we can see that the time complexity to move n disks.
Is equal to two times the time complexity of moving n minus one disks, because we are doing this two
times.
Plus one move which is moving the nth disk.
Right.
So t of n is equal to two times t of n minus one plus one.
And we know that t of one which is the time complexity.
To move one disk is equal to one because it's just directly moving that particular disk from the from
road to the two road.
Now let's try to solve this to arrive at the time complexity.
Now over here I have two times t of n minus one plus one.
And instead of t of n minus one.
Let me replace this in the same manner, because t of n minus one is going to be equal to two times
t of n minus two plus one.
And if we go ahead in this manner instead of t of n minus two, I can write.
Two times t of N minus three plus one.
And it goes on in this manner.
Right.
So this over here, this expression over here simplifies to two square into t of n minus two.
Because you have two into two into t of n minus two.
So that's this term over here plus two to the power one which is this two over here into this one over
here.
Plus one which is this one over here.
Now if you are to expand this expression over here, you will get two to the power three into t of n
minus three because you have two, two, two.
So two to the power three into t of n minus three plus two square.
Plus two to the power.
One plus one.
All right.
And then using this let's come up with the general expression.
For t of N.
Now, if I want to reach, if I want to convert this term into t of one, because we already know that
t of one is equal to one, I would have to keep doing this.
This three should be n minus one, because n minus n minus one would give me one, right?
So notice over here when there is three over here we have three over here.
So if I write t of n minus n minus one over here I would have two to the power n minus one.
And in a similar manner this would be one less, this would be one less etc..
So t of n in this way can be written as two to the power n minus one into t of one plus.
And then you keep having these terms two to the power n minus two, which is one less than this, plus
two to the power n minus one, etc. up to one and one is nothing but two to the power zero.
So this is the final time complexity.
So t of n is equal to two to the power n minus one.
And again this over here can be replaced with one because we know that t of one is one.
So t of n is two to the power n minus one plus two to the power n minus two, etcetera up to one.
So let's make some space.
So we have seen this already.
And this over here is nothing but a geometric progression because we are just keeping on multiplying
two.
So it's just one plus two plus two square etc. up to two to the power n minus one.
Now for a geometric progression, the sum up to n terms is given by a into one minus r to the power
n by one minus r, where a is the first term.
So in this case we are doing one plus two, etc. up to two to the power n minus one.
So the first term or a is equal to one.
So let's write this over here.
So we have one into and one minus and one minus.
And the next thing we need to know is r is nothing but the factor with which we are keeping on multiplying.
So one into two gives me the next term.
Two into two gives me the next term.
So r in this case is two because I'm keeping on multiplying with two.
So that's why I have R over here.
And then n over here is the total number of terms.
So over here this is two to the power zero.
This is two to the power one up to two to the power N minus one.
So zero up to n minus one.
This over here is n terms.
So that's why over here I have to write n.
So t of n is equal to one into one minus two to the power n divided by one minus two.
So this over here is minus one.
So to simplify this I can just change the sign over here and remove the minus.
So this over here is equal to two to the power n minus one.
So t of n is two to the power n minus one.
Or we can say that the time complexity is of the order of two to the power n.