1
00:00:00,530 --> 00:00:01,610
Welcome back.

2
00:00:01,610 --> 00:00:08,000
In the previous video, we discussed that the time complexity of the build heap algorithm is O of N,

3
00:00:08,000 --> 00:00:11,180
and in this video let's discuss the proof of this.

4
00:00:11,180 --> 00:00:13,850
So over here I have a perfect binary tree.

5
00:00:13,850 --> 00:00:20,960
Now remember heaps are complete binary trees right now over here in this in the last level we fill the

6
00:00:20,960 --> 00:00:22,520
nodes from left to right.

7
00:00:22,520 --> 00:00:25,670
Now let's say all the nodes are filled, so it will look like this.

8
00:00:25,670 --> 00:00:27,920
So this is how our heap will look.

9
00:00:27,920 --> 00:00:28,340
All right.

10
00:00:28,370 --> 00:00:30,740
Now let's let me separate this into levels.

11
00:00:30,740 --> 00:00:33,950
Now in the last level let's say there are n nodes.

12
00:00:33,950 --> 00:00:34,490
All right.

13
00:00:34,490 --> 00:00:40,190
Now you can notice that in the previous level there will be n by two nodes which is four over here.

14
00:00:40,190 --> 00:00:40,550
Right.

15
00:00:40,550 --> 00:00:42,440
N is equal to eight in this case.

16
00:00:42,440 --> 00:00:44,210
And n by two is equal to four.

17
00:00:44,210 --> 00:00:49,550
Now in the level which is above this there will be n by four nodes which is two.

18
00:00:49,550 --> 00:00:54,350
And over here there will be n by eight nodes which is equal to one in this case.

19
00:00:54,350 --> 00:00:56,990
Now how many levels are there over here.

20
00:00:57,140 --> 00:01:00,560
Now n is the number of nodes in the last level.

21
00:01:00,560 --> 00:01:06,530
If that is the case, if that is n, then we can say that the number of levels will be equal to log

22
00:01:06,530 --> 00:01:10,280
n right which is equal to eight, log eight over here which is equal to three.

23
00:01:10,280 --> 00:01:11,780
So there are three levels over here.

24
00:01:11,780 --> 00:01:13,310
Now this is level zero.

25
00:01:13,310 --> 00:01:14,420
This is level one.

26
00:01:14,420 --> 00:01:16,670
This is level two and this is level three.

27
00:01:17,180 --> 00:01:17,600
All right.

28
00:01:17,600 --> 00:01:20,810
So there will be log n levels which is equal to three.

29
00:01:20,810 --> 00:01:24,470
So let's just keep this aside and this is our base.

30
00:01:24,470 --> 00:01:29,210
Now let's get to look at the time complexity of the build heap algorithm.

31
00:01:29,210 --> 00:01:35,810
Now the time complexity will depend on the maximum number of swaps that we have to do right when we

32
00:01:35,810 --> 00:01:36,440
bubble down.

33
00:01:36,440 --> 00:01:42,950
So we are doing the bubble down operation or the bubble down function is called on all the internal

34
00:01:42,950 --> 00:01:43,220
nodes.

35
00:01:43,220 --> 00:01:43,490
Right.

36
00:01:43,490 --> 00:01:48,140
So again we take time for operations which are swap operations.

37
00:01:48,140 --> 00:01:51,440
So the time will depend on the maximum number of swaps.

38
00:01:51,440 --> 00:01:54,770
Again when we look at big O we are looking at an upper bound.

39
00:01:54,770 --> 00:01:55,340
All right.

40
00:01:55,340 --> 00:02:00,440
So over here in this level in for these N nodes right.

41
00:02:00,440 --> 00:02:02,000
All their children are null.

42
00:02:02,000 --> 00:02:02,180
Right.

43
00:02:02,180 --> 00:02:04,010
So they there will be no swaps.

44
00:02:04,010 --> 00:02:09,980
So this n just to make it to a pattern, I can write this n as n divided by two to the power zero,

45
00:02:09,980 --> 00:02:12,440
because two to the power zero is equal to one, right.

46
00:02:12,440 --> 00:02:17,960
So this is two to the power one and four can be written as n divided by two to the power two, etc..

47
00:02:17,960 --> 00:02:19,070
So let's go ahead.

48
00:02:19,070 --> 00:02:23,690
So in for these n nodes definitely there will be no swaps required right.

49
00:02:23,690 --> 00:02:26,900
We have already discussed that leaf nodes follow the heap property.

50
00:02:26,900 --> 00:02:33,320
So for over here the number of swaps the max number of swaps will be n divided by two to the power zero

51
00:02:33,320 --> 00:02:37,670
into zero, because for all of these, only zero swaps will be required.

52
00:02:37,670 --> 00:02:38,240
All right.

53
00:02:38,270 --> 00:02:40,910
Now what about the next level for the next level?

54
00:02:40,910 --> 00:02:44,810
For these n by two nodes there can be maximum one swap, right.

55
00:02:44,810 --> 00:02:48,440
For example, if you want to swap this you can maximum swap it one time.

56
00:02:48,440 --> 00:02:51,650
So plus n by two to the power one into one.

57
00:02:52,760 --> 00:02:55,370
Now what about these n by four nodes.

58
00:02:55,370 --> 00:02:56,900
For these n by four nodes.

59
00:02:56,900 --> 00:03:00,290
And again I can write this as n divided by two to the power two.

60
00:03:00,320 --> 00:03:02,720
There can be maximum two swaps right.

61
00:03:02,720 --> 00:03:04,670
I could either swap with one of these two.

62
00:03:04,670 --> 00:03:05,600
That's one swap.

63
00:03:05,600 --> 00:03:10,730
And then if I for example if I swap with this one I can again swap with one of these two.

64
00:03:10,730 --> 00:03:12,080
So again the second time.

65
00:03:12,080 --> 00:03:15,920
So a maximum of two swaps can be done for these n by four nodes.

66
00:03:15,920 --> 00:03:21,380
So I write plus n by two to the power two into two maximum two swaps.

67
00:03:21,380 --> 00:03:21,770
Right.

68
00:03:21,770 --> 00:03:25,370
So this goes on till we reach the root node.

69
00:03:25,370 --> 00:03:28,040
Right now there are log n levels right.

70
00:03:28,040 --> 00:03:35,240
So we can say that this goes on up to n divided by two to the power log n into log n right.

71
00:03:35,240 --> 00:03:37,640
So there can be log n swaps in this case.

72
00:03:37,640 --> 00:03:40,310
So over here we have seen log n is equal to three.

73
00:03:40,310 --> 00:03:42,530
So let's look at this root node over here.

74
00:03:42,530 --> 00:03:44,090
How many swaps can be done.

75
00:03:44,090 --> 00:03:46,130
Maximum one two and three.

76
00:03:46,130 --> 00:03:48,830
So maximum three swaps which is equal to log n.

77
00:03:48,830 --> 00:03:50,330
So that's this log n over here.

78
00:03:50,330 --> 00:03:52,580
Now why do I have two to the power log n.

79
00:03:52,580 --> 00:03:54,020
Let's look at the pattern.

80
00:03:54,500 --> 00:03:56,960
So over here we have two to the power zero.

81
00:03:56,960 --> 00:03:57,410
Right.

82
00:03:57,410 --> 00:03:59,960
And then over here we have two to the power one.

83
00:03:59,960 --> 00:04:02,360
And then over here we have two to the power two.

84
00:04:02,390 --> 00:04:03,800
So it's increasing.

85
00:04:03,800 --> 00:04:07,130
And it will go on up to two to the power log n.

86
00:04:07,130 --> 00:04:11,870
And in this case this is n by eight which is n divided by two to the power three.

87
00:04:11,870 --> 00:04:15,950
So this three over here is log n which we have seen over here is three.

88
00:04:15,950 --> 00:04:18,680
So this goes on till two to the power log n.

89
00:04:18,680 --> 00:04:21,740
So n divided by two to the power log n into log n.

90
00:04:21,740 --> 00:04:25,250
So this is the maximum number of swaps that's required.

91
00:04:25,250 --> 00:04:29,360
So time complexity will depend on the maximum number of operations.

92
00:04:29,360 --> 00:04:29,840
All right.

93
00:04:29,840 --> 00:04:34,340
So after having established this let me just clear this space and take this up.

94
00:04:34,340 --> 00:04:38,600
So we have already established that this is the time complexity right now.

95
00:04:38,600 --> 00:04:40,280
Let's try to simplify this.

96
00:04:40,730 --> 00:04:41,780
Now over here.

97
00:04:41,780 --> 00:04:43,550
This is zero into something right.

98
00:04:43,550 --> 00:04:45,020
So this becomes just zero.

99
00:04:45,020 --> 00:04:46,220
So this is zero.

100
00:04:46,220 --> 00:04:48,260
And we are just left with this part over here.

101
00:04:48,260 --> 00:04:52,130
And you can see that there is n over here everywhere in the numerator.

102
00:04:52,130 --> 00:04:55,250
So let me take this n out and simplify it.

103
00:04:55,250 --> 00:04:59,810
So this becomes one by two over here and two by two square.

104
00:04:59,810 --> 00:05:03,800
And the next term will be three by two to the power, three four by two to the power four.

105
00:05:03,800 --> 00:05:08,180
And the last term will be log n divided by two to the power log n.

106
00:05:08,180 --> 00:05:08,720
All right.

107
00:05:08,750 --> 00:05:12,200
Now let me divide the left and right hand side by two.

108
00:05:12,230 --> 00:05:14,510
So I get two by two is equal to.

109
00:05:14,510 --> 00:05:19,820
And then I have n into and I'm dividing by two or multiplying by one by two.

110
00:05:19,820 --> 00:05:20,000
Right.

111
00:05:20,000 --> 00:05:23,000
So each of these powers can be incremented by one.

112
00:05:23,000 --> 00:05:25,220
So I have one over here two over here three over here.

113
00:05:25,220 --> 00:05:30,590
So when I multiply with one by two the right hand side I just increase these by one.

114
00:05:30,590 --> 00:05:30,920
Right.

115
00:05:30,920 --> 00:05:35,600
So I get n into one by two square plus two by this.

116
00:05:35,600 --> 00:05:36,290
Two plus one.

117
00:05:36,290 --> 00:05:40,340
That is three three by two to the power, three plus one which is four, etc..

118
00:05:40,340 --> 00:05:44,780
And the last term will be log n divided by two to the power log n plus one.

119
00:05:44,780 --> 00:05:45,290
All right.

120
00:05:45,320 --> 00:05:46,970
Now let me just clear this.

121
00:05:47,560 --> 00:05:49,810
So we have tea over here and we have tea by two.

122
00:05:49,840 --> 00:05:51,100
Tea by two over here.

123
00:05:51,100 --> 00:05:53,710
Now let me just do t minus t by two.

124
00:05:53,710 --> 00:05:55,510
So we are going to subtract these two.

125
00:05:55,930 --> 00:06:01,750
Now on the left hand side when I subtract these two I get t minus t by two which is t by two itself.

126
00:06:01,750 --> 00:06:06,340
And you can see that on the right hand side I have n over here and I have n over here.

127
00:06:06,340 --> 00:06:07,480
So let me take that out.

128
00:06:07,480 --> 00:06:07,780
Right.

129
00:06:07,780 --> 00:06:09,970
So the left hand side is t by two.

130
00:06:09,970 --> 00:06:12,550
And the right hand side is n into something.

131
00:06:12,550 --> 00:06:15,970
And this something is if you just subtract what is inside the brackets.

132
00:06:15,970 --> 00:06:17,680
So we need to subtract these two.

133
00:06:18,100 --> 00:06:20,980
Now let me just write this one by two over here.

134
00:06:20,980 --> 00:06:22,450
So I have one by two over here.

135
00:06:22,450 --> 00:06:28,240
Now you can see that if I subtract these two terms they have the same denominator which is two to the

136
00:06:28,240 --> 00:06:28,870
power two.

137
00:06:28,900 --> 00:06:30,070
So I can subtract them.

138
00:06:30,070 --> 00:06:30,280
Right.

139
00:06:30,280 --> 00:06:33,040
So I just need to perform the subtraction on the numerator.

140
00:06:33,040 --> 00:06:34,840
And the denominator stays the same.

141
00:06:34,840 --> 00:06:40,870
So two divided by two square minus one divided by two square is equal to two minus one which is one

142
00:06:40,870 --> 00:06:42,310
divided by two square.

143
00:06:42,310 --> 00:06:44,740
Similarly over here for these two terms.

144
00:06:44,740 --> 00:06:47,200
Also I have two cubed as the denominator.

145
00:06:47,200 --> 00:06:48,130
So let's subtract.

146
00:06:48,130 --> 00:06:52,570
So I get three minus two divided by two cubed which is again one divided by two cube.

147
00:06:52,570 --> 00:06:54,460
And you see that there is a pattern.

148
00:06:54,460 --> 00:06:56,260
So this goes on till over here.

149
00:06:56,260 --> 00:06:59,440
Right now I take log n by two to the power log in.

150
00:06:59,440 --> 00:07:01,300
And the second last element over here.

151
00:07:01,300 --> 00:07:05,710
Now if I subtract these two I will get one divided by two to the power log n.

152
00:07:05,710 --> 00:07:08,050
Now again you can think of it in two ways.

153
00:07:08,050 --> 00:07:10,750
Notice that you have two square and you have two square.

154
00:07:10,750 --> 00:07:11,860
And the numerator is one.

155
00:07:11,860 --> 00:07:13,510
You have two cube and you have two cube.

156
00:07:13,510 --> 00:07:14,440
The numerator is one.

157
00:07:14,440 --> 00:07:18,430
So in in the similar manner you take two to the power log n as the denominator.

158
00:07:18,430 --> 00:07:19,780
And the numerator is one.

159
00:07:19,780 --> 00:07:23,350
Now another way is you can compute the previous term over here right.

160
00:07:23,350 --> 00:07:25,180
So that will be log n minus one.

161
00:07:25,180 --> 00:07:27,160
The numerator will be log n minus one.

162
00:07:27,160 --> 00:07:30,100
And the denominator will be two to the power log n right.

163
00:07:30,100 --> 00:07:32,890
So again log n minus log n minus one.

164
00:07:32,890 --> 00:07:34,180
So the numerator will be one.

165
00:07:34,180 --> 00:07:36,910
And the denominator again will be two to the power log n.

166
00:07:36,910 --> 00:07:40,090
And then we just have this one element more right.

167
00:07:40,090 --> 00:07:42,550
So again we are subtracting this minus this.

168
00:07:42,550 --> 00:07:44,380
So there will be a minus over here.

169
00:07:44,860 --> 00:07:51,130
So it's going to be minus this term which is minus log n divided by two to the power log n plus one.

170
00:07:51,130 --> 00:07:51,550
All right.

171
00:07:51,550 --> 00:07:53,380
So let's take this element over here.

172
00:07:53,380 --> 00:07:55,210
So we have this expression over here.

173
00:07:55,210 --> 00:07:57,100
And I'm just clearing the space.

174
00:07:57,100 --> 00:07:58,900
Now let's try to simplify this.

175
00:07:58,900 --> 00:08:03,520
Now if you look at this part over here you can see this is nothing but a geometric progression.

176
00:08:03,520 --> 00:08:11,200
So for a geometric progression sum up to n terms can be calculated using the formula A into one minus

177
00:08:11,200 --> 00:08:13,360
r to the power n by one minus r.

178
00:08:13,360 --> 00:08:17,890
So this is the formula to sum a geometric progression up to the nth term.

179
00:08:17,890 --> 00:08:19,690
So a is the first term.

180
00:08:19,690 --> 00:08:24,340
The second term will be a into r, the next term will be a into r into r right.

181
00:08:24,340 --> 00:08:31,390
You're just multiplying every time with r, and the nth term will be a into r to the power n minus one.

182
00:08:31,390 --> 00:08:33,610
So again this is the nth term right.

183
00:08:34,120 --> 00:08:35,260
Let me just write that over here.

184
00:08:35,260 --> 00:08:36,490
This is the nth term.

185
00:08:37,860 --> 00:08:39,750
Now you have n minus one over here.

186
00:08:39,750 --> 00:08:44,790
Because in the first term, if you if you take this as the nth term, what would be the first term?

187
00:08:44,790 --> 00:08:50,670
The first term will be a into r to the power one minus one, which is equal to a into r to the power

188
00:08:50,670 --> 00:08:51,810
zero which is equal to a.

189
00:08:51,810 --> 00:08:53,520
And that's our first term over here.

190
00:08:53,520 --> 00:08:54,930
So this is the first term.

191
00:08:54,930 --> 00:08:55,920
This is the nth term.

192
00:08:55,920 --> 00:09:03,570
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

193
00:09:03,570 --> 00:09:07,830
doing a into one minus r to the power n by one minus r.

194
00:09:07,830 --> 00:09:12,210
So this is the formula to find sum up to n terms in a geometric progression.

195
00:09:12,210 --> 00:09:16,740
And notice over here you have a geometric progression because you're just always multiplying with one

196
00:09:16,740 --> 00:09:18,180
by two to get the next term.

197
00:09:18,180 --> 00:09:18,720
All right.

198
00:09:18,720 --> 00:09:20,370
So let me just make some space over here.

199
00:09:20,370 --> 00:09:25,470
And let's try to simplify this expression using the formula which we just now saw.

200
00:09:25,470 --> 00:09:25,950
All right.

201
00:09:25,950 --> 00:09:34,050
So over here t by two is equal to n into whatever I get by simplifying this minus this term over here.

202
00:09:34,050 --> 00:09:39,600
So let's write that over here t by two is equal to n into what we get by simplifying the geometric progression

203
00:09:39,600 --> 00:09:42,420
minus log n by two to the power log n plus one.

204
00:09:42,420 --> 00:09:44,040
All right let's hold there over here.

205
00:09:44,040 --> 00:09:50,730
And let's now have a side note and try to find this expression for this geometric progression over here.

206
00:09:50,730 --> 00:09:55,230
Now over here what will be a a will be one by two which is the first term.

207
00:09:55,230 --> 00:09:55,560
Right.

208
00:09:55,560 --> 00:09:56,460
And what is r.

209
00:09:56,490 --> 00:09:58,710
We are always multiplying with one by two.

210
00:09:58,710 --> 00:09:58,920
Right.

211
00:09:58,920 --> 00:10:00,570
So r is equal to one by two.

212
00:10:00,600 --> 00:10:03,810
In this case notice that we are just multiplying always r over here.

213
00:10:03,810 --> 00:10:05,910
So we know A and we know r.

214
00:10:05,940 --> 00:10:08,070
Now let's find r to the power n.

215
00:10:08,070 --> 00:10:12,720
Now the last term is a into r to the power n minus two.

216
00:10:12,750 --> 00:10:12,930
Right.

217
00:10:12,930 --> 00:10:15,960
And a is equal to one by two a is equal to one by two.

218
00:10:15,990 --> 00:10:21,030
So I can say that the last term is one by two into r to the power n minus one.

219
00:10:21,030 --> 00:10:26,220
So one by two into r to the power n minus one n minus one is equal to this one over here, which is

220
00:10:26,220 --> 00:10:29,310
the last term which is one by two to the power log n.

221
00:10:29,310 --> 00:10:29,790
All right.

222
00:10:29,820 --> 00:10:36,000
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

223
00:10:36,000 --> 00:10:39,150
is two divided by two to the power log n.

224
00:10:39,150 --> 00:10:39,750
All right.

225
00:10:39,780 --> 00:10:43,740
Now let me multiply both the sides with one by two.

226
00:10:43,740 --> 00:10:46,650
Right again r over here r is also equal to one by two.

227
00:10:46,650 --> 00:10:46,920
Right.

228
00:10:46,920 --> 00:10:48,270
So I'm not writing it over here.

229
00:10:48,270 --> 00:10:51,240
But you can just say that this is nothing but one by two.

230
00:10:51,240 --> 00:10:52,080
Let me write it over here.

231
00:10:52,080 --> 00:10:54,360
One by two to the power n minus one.

232
00:10:54,360 --> 00:10:54,750
Right.

233
00:10:54,750 --> 00:10:59,760
So if I multiply this with one by two and the right hand side also with one by two, right.

234
00:10:59,760 --> 00:11:04,140
So I get one by two into two divided by two to the power log n.

235
00:11:04,140 --> 00:11:05,730
So these two cancel out.

236
00:11:05,730 --> 00:11:06,840
So let me write that over here.

237
00:11:06,840 --> 00:11:12,660
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

238
00:11:12,660 --> 00:11:13,080
log n.

239
00:11:13,080 --> 00:11:14,640
And these two cancel out.

240
00:11:14,640 --> 00:11:19,740
And therefore I can say r to the power n is nothing but one by two to the power log n.

241
00:11:19,740 --> 00:11:23,130
And again I'm just keeping it like this because we want it over here.

242
00:11:23,130 --> 00:11:25,080
Right now R is nothing but one by two.

243
00:11:25,110 --> 00:11:26,550
You can write it like that as well.

244
00:11:26,550 --> 00:11:31,680
So we have found that r by r to the power n is one by two to the power log n.

245
00:11:31,680 --> 00:11:33,780
Now why did I multiply with one by two.

246
00:11:33,780 --> 00:11:35,460
Because I have a minus one over here.

247
00:11:35,460 --> 00:11:35,670
Right.

248
00:11:35,670 --> 00:11:40,230
So this over here simplifies to one by two to the power n minus one plus one.

249
00:11:40,230 --> 00:11:41,280
And these cancel out.

250
00:11:41,280 --> 00:11:42,660
And I have just n over here.

251
00:11:42,660 --> 00:11:44,100
And this is nothing but r.

252
00:11:44,130 --> 00:11:44,580
All right.

253
00:11:44,580 --> 00:11:45,720
So that was just a side note.

254
00:11:45,720 --> 00:11:47,070
Let me just clear this up.

255
00:11:47,940 --> 00:11:53,820
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

256
00:11:53,820 --> 00:11:56,490
equal to one by two and r is equal to one by two.

257
00:11:56,520 --> 00:12:01,410
So let's now substitute this to this formula over here to find sum up to n terms.

258
00:12:01,410 --> 00:12:08,490
So this one over here this will be equal to one by two into one minus one by two to the power log n.

259
00:12:08,490 --> 00:12:13,080
This is r to the power n right divided by one minus r and r is one by two.

260
00:12:13,110 --> 00:12:16,620
So we have found that t by two is equal to this expression over here.

261
00:12:16,650 --> 00:12:19,290
Now let's clear the space and write this up.

262
00:12:19,290 --> 00:12:21,450
So we continue simplifying this.

263
00:12:21,450 --> 00:12:24,780
Now one minus one by two is nothing but one by two itself.

264
00:12:24,780 --> 00:12:28,140
Now we have one by two in the numerator and in the denominator right.

265
00:12:28,140 --> 00:12:29,730
So we can cancel these two.

266
00:12:30,180 --> 00:12:30,660
All right.

267
00:12:30,660 --> 00:12:32,940
So now the denominator is one.

268
00:12:32,940 --> 00:12:33,870
This is already done right.

269
00:12:33,870 --> 00:12:34,860
This is cancelled out.

270
00:12:34,860 --> 00:12:41,580
So now we just have n into one minus one by two to the power log n minus this one over here.

271
00:12:41,580 --> 00:12:43,590
Now let me just have a side note over here.

272
00:12:43,590 --> 00:12:48,750
We know that log eight to the base two is equal to three because two to the power three is equal to

273
00:12:48,750 --> 00:12:48,930
eight.

274
00:12:48,960 --> 00:12:50,670
We have discussed this previously right.

275
00:12:50,670 --> 00:12:54,540
So log eight is what what will be this value.

276
00:12:54,540 --> 00:12:56,160
This is nothing but two to the power.

277
00:12:56,160 --> 00:12:57,270
What is equal to eight.

278
00:12:57,270 --> 00:12:58,230
And we get three.

279
00:12:58,230 --> 00:13:01,830
So log eight is equal to 3 or 2 to the power three is equal to log eight.

280
00:13:01,860 --> 00:13:08,070
Now instead of this three over here let me write this log eight right over here because three is equal

281
00:13:08,070 --> 00:13:08,490
to log eight.

282
00:13:08,490 --> 00:13:12,120
So I can substitute this three with its equivalent value which is log eight.

283
00:13:12,120 --> 00:13:16,290
So I can say two to the power log eight is equal to this eight.

284
00:13:16,290 --> 00:13:16,470
Right.

285
00:13:16,470 --> 00:13:19,500
So I can say two to the power log eight is equal to eight.

286
00:13:19,500 --> 00:13:20,700
Now instead of eight.

287
00:13:20,700 --> 00:13:25,290
If I write n you can see that two to the power log n is nothing but n.

288
00:13:25,290 --> 00:13:25,710
All right.

289
00:13:25,710 --> 00:13:31,890
So this side note was just to prove to you that two to the power log n is equal to n because the base

290
00:13:31,890 --> 00:13:33,450
over here is two itself.

291
00:13:33,450 --> 00:13:34,170
All right.

292
00:13:34,590 --> 00:13:36,360
So two to the power log n is n.

293
00:13:36,360 --> 00:13:38,340
Now let's substitute that over here.

294
00:13:38,340 --> 00:13:40,140
So we have two to the power log n over here.

295
00:13:40,140 --> 00:13:41,970
So instead of this I can write n.

296
00:13:41,970 --> 00:13:47,100
So this simplifies to two by two is equal to n into one minus one by n.

297
00:13:47,100 --> 00:13:51,240
Because this one by two to the power log n is nothing but one by n right.

298
00:13:51,240 --> 00:13:57,150
So this has been simplified to one by n minus log n divided by two to the power log n plus one.

299
00:13:57,150 --> 00:13:58,590
Now let's try to simplify this.

300
00:13:58,590 --> 00:14:03,900
Also two to the power log n plus one can be written as two to the power log n into two.

301
00:14:03,900 --> 00:14:04,260
Right.

302
00:14:04,260 --> 00:14:06,090
So again why is that so quick.

303
00:14:06,090 --> 00:14:12,180
Side note if you have two to the power a into two to the power B, this is nothing but two to the power

304
00:14:12,180 --> 00:14:14,490
A plus B so we are using this property.

305
00:14:14,490 --> 00:14:19,200
So two to the power log n plus one is two to the power one into two to the power log n.

306
00:14:19,200 --> 00:14:24,450
So if you simplify from the right hand side to the left hand side you we can say two to the power one

307
00:14:24,450 --> 00:14:25,530
plus log n right.

308
00:14:25,530 --> 00:14:26,070
All right.

309
00:14:26,070 --> 00:14:27,750
So that was just a side note.

310
00:14:28,230 --> 00:14:33,570
Now we are simplifying two to the power log n plus one as two into two to the power log n.

311
00:14:33,570 --> 00:14:38,820
Now let's write instead of two to the power log n we know that that's equal to n.

312
00:14:38,820 --> 00:14:44,670
So this denominator over here two to the power log n plus one is nothing but two into n right.

313
00:14:44,670 --> 00:14:46,380
So this is nothing but two into n.

314
00:14:46,380 --> 00:14:48,870
Now let's take the let's open the bracket.

315
00:14:48,870 --> 00:14:50,070
And take the n inside.

316
00:14:50,070 --> 00:14:55,920
So n into one gives me n one by n into n is one and n into log n by two.

317
00:14:55,920 --> 00:14:57,930
N is nothing but log n by two.

318
00:14:57,960 --> 00:14:59,490
So this simplifies to this right.

319
00:14:59,490 --> 00:15:01,530
So we have two by two is equal to this.

320
00:15:01,530 --> 00:15:03,960
Now let's take the two to the right hand side.

321
00:15:03,960 --> 00:15:08,040
So we get t is equal to two n minus two minus log n.

322
00:15:08,160 --> 00:15:08,610
All right.

323
00:15:08,610 --> 00:15:09,780
So let's make some space.

324
00:15:09,780 --> 00:15:11,670
We have found the expression for t.

325
00:15:11,700 --> 00:15:14,190
Now over here you can see that two is a constant.

326
00:15:14,190 --> 00:15:19,560
So this can be just removed when we find Big-O now among two n and log n right.

327
00:15:19,560 --> 00:15:22,590
We know that n dominates or two n dominates.

328
00:15:22,590 --> 00:15:22,980
Right.

329
00:15:22,980 --> 00:15:24,690
So again why is that.

330
00:15:24,690 --> 00:15:28,710
So we have seen the uh the time complexity sheet.

331
00:15:28,710 --> 00:15:28,980
Right.

332
00:15:28,980 --> 00:15:31,710
So over here n goes like this.

333
00:15:31,710 --> 00:15:33,840
The number of operations if it's o of n right.

334
00:15:33,840 --> 00:15:36,210
If it's o of log n, it goes very slowly.

335
00:15:36,210 --> 00:15:36,540
Right.

336
00:15:36,540 --> 00:15:37,080
Like this.

337
00:15:37,080 --> 00:15:38,370
So this dominates.

338
00:15:38,370 --> 00:15:39,810
So this also can be removed.

339
00:15:39,810 --> 00:15:41,010
And two is a constant.

340
00:15:41,010 --> 00:15:47,730
So we can say that the time complexity of the build heap algorithm is O of n.