1
00:00:00,140 --> 00:00:01,160
Welcome back.

2
00:00:01,160 --> 00:00:08,270
Let's now take a look at the time and space complexity of the approach that we came up with for solving

3
00:00:08,270 --> 00:00:09,740
the Tower of Hanoi problem.

4
00:00:09,740 --> 00:00:11,750
Over here we have the recursion tree.

5
00:00:11,780 --> 00:00:19,310
Notice that the number of print statements is equal to the number of moves required, because again,

6
00:00:19,310 --> 00:00:20,810
that's how we designed it, right?

7
00:00:20,810 --> 00:00:25,880
We always wanted to have a print statement when a move is made.

8
00:00:26,330 --> 00:00:30,020
First let's now think about the space complexity.

9
00:00:30,020 --> 00:00:38,180
The space complexity of this solution is going to be of the order of N because of the space used on

10
00:00:38,180 --> 00:00:40,040
the recursive call stack.

11
00:00:40,040 --> 00:00:47,510
Notice over here that at any point, the maximum number of simultaneous calls on the recursive call

12
00:00:47,510 --> 00:00:52,580
stack is going to be of the order of n, where n is the number of disks.

13
00:00:52,580 --> 00:00:53,000
Over.

14
00:00:53,000 --> 00:00:58,460
Here we call this function with n equal to three, and over here we have n is equal to two.

15
00:00:58,460 --> 00:01:00,830
And over here we have n is equal to one.

16
00:01:00,830 --> 00:01:06,680
So that's why the space complexity of this solution is of the order of n.

17
00:01:07,070 --> 00:01:12,980
When it comes to the time complexity, it's going to be of the order of two to the power n.

18
00:01:12,980 --> 00:01:16,220
Now there are two ways that we can think about this.

19
00:01:16,220 --> 00:01:19,490
First, let's take a look at the intuitive approach.

20
00:01:19,490 --> 00:01:25,700
If there is only one disk, we have seen that we just have to make one move, which is to move that

21
00:01:25,700 --> 00:01:29,600
particular disk from the from road to the two road.

22
00:01:29,600 --> 00:01:31,220
So this is something that we have seen.

23
00:01:31,220 --> 00:01:35,480
Now if there are two disks, notice that we have to do three moves.

24
00:01:35,480 --> 00:01:41,180
And if there are three disks which is the case over here, we have to do seven moves.

25
00:01:41,780 --> 00:01:45,320
That's 1234567.

26
00:01:45,320 --> 00:01:54,620
So if you take a look at this pattern 137 this pattern over here is actually two to the power n minus

27
00:01:54,620 --> 00:01:57,590
one where n is the number of disks.

28
00:01:57,590 --> 00:02:04,340
So if you have one disk so that's two to the power one minus one which is two minus one which is one

29
00:02:04,340 --> 00:02:04,700
move.

30
00:02:04,700 --> 00:02:11,390
If you have two disks that's two to the power two minus one which is four minus one which is three moves.

31
00:02:11,390 --> 00:02:17,840
And for three disks that's two to the power, three minus one which is eight minus one which is seven

32
00:02:17,840 --> 00:02:18,230
moves.

33
00:02:18,230 --> 00:02:23,030
So that's why the number of moves is two to the power n minus one.

34
00:02:23,030 --> 00:02:30,890
And hence the time complexity would be of the order of two to the power n, because again in each call

35
00:02:30,890 --> 00:02:33,560
we are just doing some constant time operations.

36
00:02:33,560 --> 00:02:38,990
So the number of calls that we are making will be of the order of two to the power n.

37
00:02:38,990 --> 00:02:44,510
Now there is one more way that we can think about when we take a look at the time complexity.

38
00:02:45,110 --> 00:02:54,110
We have discussed that to move n disks, we are actually first moving n minus one disks from the from

39
00:02:54,110 --> 00:02:56,540
rod to the auxiliary rod.

40
00:02:56,540 --> 00:03:02,270
Then we are going to move the nth disk from the from rod to the two rod.

41
00:03:02,270 --> 00:03:08,600
And finally we are going to again move n minus one disks from the auxiliary rod to the two rod.

42
00:03:08,840 --> 00:03:10,730
This is what we have discussed right now.

43
00:03:10,730 --> 00:03:17,090
If we take a look at the time complexity of this, we can see that the time complexity to move n disks.

44
00:03:17,740 --> 00:03:24,520
Is equal to two times the time complexity of moving n minus one disks, because we are doing this two

45
00:03:24,520 --> 00:03:25,240
times.

46
00:03:26,180 --> 00:03:30,440
Plus one move which is moving the nth disk.

47
00:03:30,440 --> 00:03:30,860
Right.

48
00:03:30,860 --> 00:03:36,530
So t of n is equal to two times t of n minus one plus one.

49
00:03:36,530 --> 00:03:40,850
And we know that t of one which is the time complexity.

50
00:03:40,850 --> 00:03:47,780
To move one disk is equal to one because it's just directly moving that particular disk from the from

51
00:03:47,780 --> 00:03:49,370
road to the two road.

52
00:03:49,400 --> 00:03:53,510
Now let's try to solve this to arrive at the time complexity.

53
00:03:53,540 --> 00:03:58,280
Now over here I have two times t of n minus one plus one.

54
00:03:58,280 --> 00:04:01,040
And instead of t of n minus one.

55
00:04:01,040 --> 00:04:07,880
Let me replace this in the same manner, because t of n minus one is going to be equal to two times

56
00:04:07,910 --> 00:04:10,850
t of n minus two plus one.

57
00:04:11,880 --> 00:04:17,670
And if we go ahead in this manner instead of t of n minus two, I can write.

58
00:04:18,810 --> 00:04:23,580
Two times t of N minus three plus one.

59
00:04:23,580 --> 00:04:24,930
And it goes on in this manner.

60
00:04:24,930 --> 00:04:25,260
Right.

61
00:04:25,260 --> 00:04:34,170
So this over here, this expression over here simplifies to two square into t of n minus two.

62
00:04:34,170 --> 00:04:37,080
Because you have two into two into t of n minus two.

63
00:04:37,110 --> 00:04:44,640
So that's this term over here plus two to the power one which is this two over here into this one over

64
00:04:44,640 --> 00:04:45,000
here.

65
00:04:45,000 --> 00:04:47,160
Plus one which is this one over here.

66
00:04:47,160 --> 00:04:54,180
Now if you are to expand this expression over here, you will get two to the power three into t of n

67
00:04:54,180 --> 00:04:56,970
minus three because you have two, two, two.

68
00:04:57,000 --> 00:05:01,890
So two to the power three into t of n minus three plus two square.

69
00:05:02,600 --> 00:05:03,650
Plus two to the power.

70
00:05:03,650 --> 00:05:05,000
One plus one.

71
00:05:05,120 --> 00:05:05,870
All right.

72
00:05:05,870 --> 00:05:10,580
And then using this let's come up with the general expression.

73
00:05:11,230 --> 00:05:12,760
For t of N.

74
00:05:13,060 --> 00:05:20,740
Now, if I want to reach, if I want to convert this term into t of one, because we already know that

75
00:05:20,740 --> 00:05:24,520
t of one is equal to one, I would have to keep doing this.

76
00:05:24,520 --> 00:05:32,230
This three should be n minus one, because n minus n minus one would give me one, right?

77
00:05:32,230 --> 00:05:35,830
So notice over here when there is three over here we have three over here.

78
00:05:35,830 --> 00:05:43,600
So if I write t of n minus n minus one over here I would have two to the power n minus one.

79
00:05:43,600 --> 00:05:48,220
And in a similar manner this would be one less, this would be one less etc..

80
00:05:48,220 --> 00:05:56,350
So t of n in this way can be written as two to the power n minus one into t of one plus.

81
00:05:56,350 --> 00:06:02,110
And then you keep having these terms two to the power n minus two, which is one less than this, plus

82
00:06:02,110 --> 00:06:08,020
two to the power n minus one, etc. up to one and one is nothing but two to the power zero.

83
00:06:08,020 --> 00:06:11,860
So this is the final time complexity.

84
00:06:11,860 --> 00:06:17,260
So t of n is equal to two to the power n minus one.

85
00:06:17,260 --> 00:06:21,970
And again this over here can be replaced with one because we know that t of one is one.

86
00:06:21,970 --> 00:06:28,600
So t of n is two to the power n minus one plus two to the power n minus two, etcetera up to one.

87
00:06:28,600 --> 00:06:30,070
So let's make some space.

88
00:06:30,070 --> 00:06:31,840
So we have seen this already.

89
00:06:31,840 --> 00:06:38,140
And this over here is nothing but a geometric progression because we are just keeping on multiplying

90
00:06:38,170 --> 00:06:38,560
two.

91
00:06:38,590 --> 00:06:44,770
So it's just one plus two plus two square etc. up to two to the power n minus one.

92
00:06:44,770 --> 00:06:53,230
Now for a geometric progression, the sum up to n terms is given by a into one minus r to the power

93
00:06:53,230 --> 00:06:57,070
n by one minus r, where a is the first term.

94
00:06:57,070 --> 00:07:03,340
So in this case we are doing one plus two, etc. up to two to the power n minus one.

95
00:07:03,340 --> 00:07:07,060
So the first term or a is equal to one.

96
00:07:07,060 --> 00:07:08,440
So let's write this over here.

97
00:07:08,440 --> 00:07:13,360
So we have one into and one minus and one minus.

98
00:07:13,360 --> 00:07:19,900
And the next thing we need to know is r is nothing but the factor with which we are keeping on multiplying.

99
00:07:19,900 --> 00:07:22,720
So one into two gives me the next term.

100
00:07:22,720 --> 00:07:25,990
Two into two gives me the next term.

101
00:07:25,990 --> 00:07:30,670
So r in this case is two because I'm keeping on multiplying with two.

102
00:07:30,700 --> 00:07:32,440
So that's why I have R over here.

103
00:07:32,440 --> 00:07:35,950
And then n over here is the total number of terms.

104
00:07:35,950 --> 00:07:38,110
So over here this is two to the power zero.

105
00:07:38,110 --> 00:07:42,340
This is two to the power one up to two to the power N minus one.

106
00:07:42,340 --> 00:07:45,250
So zero up to n minus one.

107
00:07:45,250 --> 00:07:47,950
This over here is n terms.

108
00:07:47,950 --> 00:07:50,770
So that's why over here I have to write n.

109
00:07:50,770 --> 00:07:57,910
So t of n is equal to one into one minus two to the power n divided by one minus two.

110
00:07:57,940 --> 00:08:00,190
So this over here is minus one.

111
00:08:00,190 --> 00:08:06,760
So to simplify this I can just change the sign over here and remove the minus.

112
00:08:06,760 --> 00:08:10,930
So this over here is equal to two to the power n minus one.

113
00:08:10,930 --> 00:08:14,140
So t of n is two to the power n minus one.

114
00:08:14,140 --> 00:08:19,990
Or we can say that the time complexity is of the order of two to the power n.