1
00:00:00,520 --> 00:00:01,600
Welcome back.

2
00:00:01,600 --> 00:00:04,750
So far we have understood how the quicksort works.

3
00:00:04,750 --> 00:00:05,170
All right.

4
00:00:05,200 --> 00:00:10,570
Now over here, before we go ahead and code our solution, let's look at the time complexity of the

5
00:00:10,570 --> 00:00:11,230
quicksort.

6
00:00:11,230 --> 00:00:14,320
And let's look at the best case and the worst case.

7
00:00:14,320 --> 00:00:20,110
And we will try to think of a few recommendations to avoid the worst case as much as possible.

8
00:00:20,140 --> 00:00:25,000
Now we have seen that the quicksort works by taking an element as pivot.

9
00:00:25,000 --> 00:00:30,550
And then we find the correct position where that pivot element should be after the array is sorted.

10
00:00:30,550 --> 00:00:35,500
And then we will recursively call the quicksort on the left side and the right side right.

11
00:00:35,530 --> 00:00:38,560
Now let's say we are given an array of size n.

12
00:00:38,680 --> 00:00:42,400
And let's say the pivot that we choose is the median.

13
00:00:42,400 --> 00:00:46,150
The median is nothing but the middle element of the given array, right.

14
00:00:46,180 --> 00:00:47,410
Now what will happen?

15
00:00:47,410 --> 00:00:53,440
The left side and the right side of the array now will have almost n by two elements right.

16
00:00:53,920 --> 00:00:55,060
Let's look at it over here.

17
00:00:55,060 --> 00:00:56,260
Let's say this is the array.

18
00:00:56,290 --> 00:01:00,460
Now we pick that the pivot is the median or the middle value.

19
00:01:00,460 --> 00:01:03,760
So we fix the pivot over here because it's the middle value.

20
00:01:03,760 --> 00:01:08,470
So its correct position after the array is sorted will be in the middle of the given array.

21
00:01:08,470 --> 00:01:08,770
Right.

22
00:01:08,770 --> 00:01:10,150
So we fix it over here.

23
00:01:10,150 --> 00:01:13,240
Now we will have let's say this is one element.

24
00:01:13,240 --> 00:01:15,730
This the total size was n elements.

25
00:01:15,730 --> 00:01:21,670
Now over here we will have the remaining elements in these two sides will be n minus one right.

26
00:01:21,670 --> 00:01:23,560
And half of it will be over here.

27
00:01:23,560 --> 00:01:25,300
And half of it will be over here.

28
00:01:25,300 --> 00:01:29,860
So over here we will have n minus one by two elements which is almost n by two elements.

29
00:01:29,860 --> 00:01:30,220
Right.

30
00:01:30,220 --> 00:01:31,540
So I'm just avoiding this.

31
00:01:31,540 --> 00:01:31,990
Right.

32
00:01:31,990 --> 00:01:35,110
And over here also we will have n by two elements.

33
00:01:36,360 --> 00:01:36,810
All right.

34
00:01:36,810 --> 00:01:39,240
Now let's say this happens again and again.

35
00:01:39,240 --> 00:01:40,470
Let me just clear this up.

36
00:01:40,470 --> 00:01:42,420
Let's say this happens again and again.

37
00:01:42,420 --> 00:01:45,630
That is we always pick the pivot as the median.

38
00:01:45,630 --> 00:01:45,990
All right.

39
00:01:45,990 --> 00:01:52,950
So this part over here will again be subdivided subdivided into two parts of n by four and n by four.

40
00:01:52,950 --> 00:01:56,970
And we are recursively calling the quicksort algorithm on these subarrays.

41
00:01:56,970 --> 00:01:58,470
Right again over here.

42
00:01:58,470 --> 00:02:01,680
Also we will be dividing it into n by four and n by four.

43
00:02:01,680 --> 00:02:05,970
And this will keep going till the size of the array is one.

44
00:02:05,970 --> 00:02:09,240
And again an array of size one is already sorted.

45
00:02:09,240 --> 00:02:10,230
So it will return.

46
00:02:10,230 --> 00:02:12,870
At this point it will no longer call the quicksort right.

47
00:02:12,870 --> 00:02:16,620
So this will go on till we get the size of the array as one.

48
00:02:16,620 --> 00:02:20,910
Now let's try to find out the depth of this tree.

49
00:02:20,910 --> 00:02:21,270
Right.

50
00:02:21,270 --> 00:02:26,340
So you can see over here we have n which is nothing but n divided by two to the power zero.

51
00:02:26,340 --> 00:02:31,470
Remember two to the power zero is equal to one right x to the power zero is equal to one.

52
00:02:31,470 --> 00:02:33,750
Like if you take two to the power zero that's one.

53
00:02:33,930 --> 00:02:34,890
Any any number.

54
00:02:34,890 --> 00:02:38,310
If you just raise it to the power zero you will get one as the value.

55
00:02:38,310 --> 00:02:38,820
All right.

56
00:02:38,820 --> 00:02:40,440
So that was just a side note.

57
00:02:40,440 --> 00:02:42,420
So over here the size is n.

58
00:02:42,420 --> 00:02:44,430
Let's we are trying to make a pattern of this.

59
00:02:44,430 --> 00:02:49,050
So n is nothing but two I can write n as n by one right.

60
00:02:49,050 --> 00:02:52,740
And n by one is nothing but n by two to the power zero.

61
00:02:52,740 --> 00:02:52,950
Right.

62
00:02:52,950 --> 00:02:54,630
I'm just making this into a pattern.

63
00:02:54,630 --> 00:02:57,630
So over here we have n divided by two to the power zero.

64
00:02:57,630 --> 00:03:01,200
Over here we have n divided by two to the power one right.

65
00:03:01,260 --> 00:03:08,040
This is n divided by two to the power one over here n by four I can write n by four as n divided by

66
00:03:08,040 --> 00:03:09,090
two to the power two.

67
00:03:09,120 --> 00:03:10,560
So there is a pattern right?

68
00:03:10,560 --> 00:03:16,140
We have n divided by two to the power zero n divided by two to the power one n divided by two to the

69
00:03:16,140 --> 00:03:16,800
power two.

70
00:03:16,800 --> 00:03:19,740
And this goes on like that right till we get to one.

71
00:03:19,740 --> 00:03:25,350
So this over here, I can write it as n divided by two to the power k right.

72
00:03:25,350 --> 00:03:26,430
Because of the pattern.

73
00:03:26,430 --> 00:03:26,760
Right.

74
00:03:26,760 --> 00:03:29,820
So I can write this as n divided by two to the power k.

75
00:03:29,820 --> 00:03:35,490
And that has to be equal to one, because we know we stop recursively calling the quicksort algorithm

76
00:03:35,490 --> 00:03:37,440
when the size of the array is equal to one.

77
00:03:37,440 --> 00:03:41,070
So n divided by two to the power k is equal to one, right.

78
00:03:41,070 --> 00:03:42,990
So let me just clear this up.

79
00:03:43,870 --> 00:03:46,150
So let's try to solve this.

80
00:03:46,150 --> 00:03:51,760
Now, can we find the depth of the, uh, this this tree over here?

81
00:03:51,760 --> 00:03:52,120
Right.

82
00:03:52,120 --> 00:03:53,350
What's the depth over here?

83
00:03:53,350 --> 00:03:55,210
N by two to the power k is equal to one.

84
00:03:55,210 --> 00:03:57,670
So I can say two to the power k is equal to one.

85
00:03:57,670 --> 00:04:01,660
Now if this is the case then k is nothing but log n right.

86
00:04:01,660 --> 00:04:07,090
So we have seen that in the uh in the bigger video where we discussed about log n also.

87
00:04:07,090 --> 00:04:07,480
Right.

88
00:04:07,480 --> 00:04:11,770
So if two to the power k is equal to n then k is equal to log n.

89
00:04:11,770 --> 00:04:12,460
Again.

90
00:04:12,520 --> 00:04:14,680
Uh we have separately discussed this already.

91
00:04:14,680 --> 00:04:16,990
So I'm not discussing this again over here.

92
00:04:16,990 --> 00:04:22,810
So we have found that the number of levels in this case is equal to log n.

93
00:04:22,810 --> 00:04:23,410
Right.

94
00:04:24,010 --> 00:04:24,490
Okay.

95
00:04:24,490 --> 00:04:28,270
And now when we look at each level so this is the number of levels.

96
00:04:28,270 --> 00:04:31,600
Now when we look at each level for example this is one level right.

97
00:04:31,600 --> 00:04:38,710
So over here in each level the partition algorithm will do n comparisons.

98
00:04:38,710 --> 00:04:39,250
Right.

99
00:04:39,250 --> 00:04:42,940
The partition algorithm will do n comparisons to find why.

100
00:04:42,940 --> 00:04:47,320
Why will this do n comparisons to find the correct position of the pivot right.

101
00:04:47,320 --> 00:04:49,030
The pivot has the correct index.

102
00:04:49,030 --> 00:04:54,370
We have to place the pivot at the correct index and find that correct place, so that we can go ahead

103
00:04:54,370 --> 00:04:56,200
and recursively call the quicksort.

104
00:04:56,200 --> 00:05:02,290
And again divide n by two into n by four and n by four, which is left and right side of the pivot right.

105
00:05:02,290 --> 00:05:03,790
The pivot element will be fixed.

106
00:05:03,790 --> 00:05:08,350
And then the left side of that pivot will be an array of n by four size.

107
00:05:08,350 --> 00:05:10,630
And the right side will be an array of n by four size.

108
00:05:10,630 --> 00:05:17,560
So in each level, the partition algorithm will do n comparisons to find the pivot index and to place

109
00:05:17,560 --> 00:05:19,300
the pivot at the right index.

110
00:05:19,300 --> 00:05:22,870
So we are doing n comparisons in each level.

111
00:05:22,870 --> 00:05:25,360
And how many levels do we have.

112
00:05:25,360 --> 00:05:28,360
You can see that we have log n levels right.

113
00:05:28,360 --> 00:05:29,140
In this case.

114
00:05:29,140 --> 00:05:32,890
The case is where we always picked the pivot as the middle value.

115
00:05:32,890 --> 00:05:36,160
So in this case there will be log n levels right.

116
00:05:36,160 --> 00:05:39,520
So this is nothing but like a rectangle right.

117
00:05:39,520 --> 00:05:43,540
We have in each level n comparisons and we have n levels.

118
00:05:43,540 --> 00:05:52,240
So if you have a rectangle where the width is log n and the length is n, what is the area that would

119
00:05:52,240 --> 00:05:53,680
be n into log n, right.

120
00:05:53,680 --> 00:05:55,390
The same thing applies over here.

121
00:05:55,390 --> 00:06:00,640
We have n, we have log n levels and in each level we are doing n comparisons.

122
00:06:00,640 --> 00:06:04,150
So the total number of comparisons will be n into log n.

123
00:06:04,150 --> 00:06:11,830
So the time complexity of the quicksort that we have discussed is O of n log n or order of n log n.

124
00:06:11,830 --> 00:06:12,310
All right.

125
00:06:12,310 --> 00:06:14,020
So that's the time complexity.

126
00:06:14,020 --> 00:06:18,520
So we have seen that the time complexity of the quicksort is O of n log n.

127
00:06:18,520 --> 00:06:21,250
But we got this with an assumption right.

128
00:06:21,250 --> 00:06:25,540
The assumption was that the partitioning always happens in the middle.

129
00:06:25,540 --> 00:06:30,430
So this was the assumption based on which we got the time complexity as o of n log n.

130
00:06:30,430 --> 00:06:36,340
Now this is the best case scenario right now let's take a look at the worst case scenario so that we

131
00:06:36,340 --> 00:06:38,560
can understand that this is the best case scenario.

132
00:06:38,560 --> 00:06:41,080
It makes it easy if you look at the worst case scenario.

133
00:06:41,080 --> 00:06:43,570
Now what is the worst case scenario?

134
00:06:43,570 --> 00:06:50,920
If you always pick the pivot as the minimum or the maximum, then that would be the worst case.

135
00:06:50,920 --> 00:06:52,330
Let's try to visualize this.

136
00:06:52,330 --> 00:06:55,540
Let's say the given array is one, two, three, four, five.

137
00:06:55,540 --> 00:06:59,140
And let's say we always pick the first value as the pivot.

138
00:06:59,140 --> 00:06:59,500
All right.

139
00:06:59,500 --> 00:07:01,840
So this array over here is already sorted.

140
00:07:02,320 --> 00:07:03,820
So we are taking a sorted array.

141
00:07:03,820 --> 00:07:06,370
And we always pick the first element as the pivot.

142
00:07:06,370 --> 00:07:09,130
So in this case one is the pivot right.

143
00:07:09,130 --> 00:07:10,450
So what will happen.

144
00:07:10,450 --> 00:07:13,990
Partitioning will always happen at the beginning right.

145
00:07:13,990 --> 00:07:16,120
So this is already in its correct place.

146
00:07:16,120 --> 00:07:20,740
So when we call the quicksort on this array it will find this as the pivot.

147
00:07:20,740 --> 00:07:24,190
It will fix this over here and it will return this index right.

148
00:07:24,190 --> 00:07:25,720
So there is nothing on its left.

149
00:07:25,720 --> 00:07:29,800
So in the right on its right it will it will call the quicksort on this part.

150
00:07:29,800 --> 00:07:31,090
Let's take a look at it.

151
00:07:31,950 --> 00:07:37,650
So we have seen that when we are getting a sorted array, the partitioning in this case always happens

152
00:07:37,650 --> 00:07:41,370
at the beginning because we are taking the pivot at the beginning of the given array.

153
00:07:41,370 --> 00:07:41,700
Right.

154
00:07:41,700 --> 00:07:43,050
So let's visualize this.

155
00:07:43,050 --> 00:07:45,270
So we have the array 12345.

156
00:07:45,270 --> 00:07:51,180
So we call the quicksort on this array we fix the position of one and we return the pivot index.

157
00:07:51,180 --> 00:07:54,360
Now we call the quicksort on this part 2345.

158
00:07:54,360 --> 00:07:54,810
Right.

159
00:07:54,810 --> 00:07:55,980
Again we fix.

160
00:07:55,980 --> 00:07:58,110
So at this point one was fixed.

161
00:07:58,140 --> 00:08:00,390
Now when we call it again we will fix two.

162
00:08:00,390 --> 00:08:03,270
And again we will call the quicksort on 345.

163
00:08:03,270 --> 00:08:05,040
We will fix the position of three.

164
00:08:05,040 --> 00:08:07,260
So these three are fixed by now.

165
00:08:07,260 --> 00:08:09,720
Again we will call the quicksort with four five.

166
00:08:10,300 --> 00:08:15,730
And this will keep on happening till we get to the size of the array as one.

167
00:08:15,730 --> 00:08:16,120
Right?

168
00:08:16,120 --> 00:08:19,570
So over here let's say we have n elements.

169
00:08:19,570 --> 00:08:23,650
So in this case we will do n operations or n comparisons.

170
00:08:23,650 --> 00:08:27,010
And in the next level we will do n minus one comparisons.

171
00:08:27,010 --> 00:08:29,500
In the next level we will do n minus two comparisons.

172
00:08:29,500 --> 00:08:31,450
And this will go on till one.

173
00:08:31,450 --> 00:08:31,870
Right.

174
00:08:31,870 --> 00:08:38,050
So the total number of operations that we have to do over here is n plus n minus one plus n minus two

175
00:08:38,050 --> 00:08:39,460
etc. up to one.

176
00:08:39,460 --> 00:08:39,760
Right.

177
00:08:39,760 --> 00:08:40,960
So we are adding these up.

178
00:08:40,960 --> 00:08:43,120
This is n this is n minus one.

179
00:08:43,900 --> 00:08:50,590
This is n minus two, etc. so we add all of these up and n plus n minus one plus n minus two up to one.

180
00:08:50,590 --> 00:08:54,400
This is nothing but n into n plus one by two right?

181
00:08:55,000 --> 00:08:57,400
This is uh just sum of elements, right?

182
00:08:57,400 --> 00:09:02,230
For example, if you have one plus two plus three plus four plus five.

183
00:09:02,230 --> 00:09:09,070
So you can find this by doing n into n plus one by two which is five into five plus one which is six

184
00:09:09,070 --> 00:09:09,550
by two.

185
00:09:09,550 --> 00:09:09,880
Right.

186
00:09:09,880 --> 00:09:12,580
So if you do that you will get the answer as 15.

187
00:09:12,580 --> 00:09:13,690
Now let's sum it up.

188
00:09:13,690 --> 00:09:14,890
One plus two is three.

189
00:09:14,890 --> 00:09:16,120
Three plus three is six.

190
00:09:16,120 --> 00:09:18,790
Six plus four is ten and ten plus five is 15.

191
00:09:18,790 --> 00:09:20,290
Which is this 15 over here.

192
00:09:20,290 --> 00:09:22,690
So one plus two plus three up to n.

193
00:09:22,690 --> 00:09:25,720
That can be written as n into n plus one by two.

194
00:09:25,720 --> 00:09:28,660
So that's the number of operations that we are getting in this case.

195
00:09:28,660 --> 00:09:34,060
And this is what this is n square by two plus n by two.

196
00:09:34,060 --> 00:09:34,300
Right.

197
00:09:34,300 --> 00:09:37,360
If we simplify this now this is the dominating factor.

198
00:09:37,360 --> 00:09:37,750
Right.

199
00:09:37,750 --> 00:09:41,140
So we can neglect this and we can neglect the constant also.

200
00:09:41,140 --> 00:09:44,680
So this over here will be an order of n square.

201
00:09:44,680 --> 00:09:45,130
Right.

202
00:09:45,130 --> 00:09:50,530
So the time complexity of the worst case of quicksort is O of n square which is not good.

203
00:09:50,530 --> 00:09:50,830
Right.

204
00:09:50,830 --> 00:09:53,980
So the best case we have seen is O of n log n.

205
00:09:53,980 --> 00:09:58,540
And the worst case which we have seen over here is O of n square.

206
00:09:59,530 --> 00:10:00,040
All right.

207
00:10:00,040 --> 00:10:05,650
So we have seen that the time complexity of the quicksort is O of n log n, which is the best case.

208
00:10:05,650 --> 00:10:08,290
And the worst case is O of n squared.

209
00:10:08,320 --> 00:10:12,640
Now the average time complexity of the quicksort is also O of n log n.

210
00:10:12,640 --> 00:10:15,370
And that involves a lot of maths to calculate it.

211
00:10:15,370 --> 00:10:19,360
And you can check Wikipedia if you want if you're interested to look at the math.

212
00:10:19,360 --> 00:10:21,850
But typically that's beyond the scope of any interview.

213
00:10:21,850 --> 00:10:23,530
So we are not going to cover it over here.

214
00:10:23,530 --> 00:10:29,620
So for the quicksort the best and average time complexity is O of n log n.

215
00:10:29,620 --> 00:10:32,680
And the worst time complexity is O of n squared.

216
00:10:32,710 --> 00:10:40,060
Now let's look at a few recommendations by which we could implement to try to avoid the worst case.

217
00:10:40,600 --> 00:10:40,990
Right.

218
00:10:40,990 --> 00:10:42,340
So this happened.

219
00:10:42,340 --> 00:10:48,280
For this what you can do is always pick the middle element as pivot or the or you can pick a random

220
00:10:48,280 --> 00:10:49,330
element as the pivot.

221
00:10:49,330 --> 00:10:50,590
Now let's think of it right.

222
00:10:50,590 --> 00:10:52,600
So we had a sorted array.

223
00:10:52,600 --> 00:10:55,270
That's when the worst case happened.

224
00:10:55,270 --> 00:10:55,660
Right.

225
00:10:55,660 --> 00:11:01,510
And in case of a sorted array, if you are picking always the first element as pivot, or if you are

226
00:11:01,510 --> 00:11:06,610
picking always the last element as pivot, we will get O of n square time complexity.

227
00:11:06,610 --> 00:11:07,900
We've already seen that right.

228
00:11:07,900 --> 00:11:14,770
So to avoid this we it's generally recommended that you pick the middle element as pivot.

229
00:11:14,800 --> 00:11:15,730
Now why is that.

230
00:11:15,730 --> 00:11:17,110
So it's easy.

231
00:11:17,110 --> 00:11:18,520
Let's think of it in this way.

232
00:11:18,520 --> 00:11:21,820
Is it probable that you will be given a sorted list?

233
00:11:21,820 --> 00:11:22,150
Right.

234
00:11:22,150 --> 00:11:24,100
This happens when you're given a sorted list.

235
00:11:24,100 --> 00:11:30,160
So is it possible that the array which which we are asked to sort is already sorted, or the data which

236
00:11:30,160 --> 00:11:32,290
is given to us, which is to be sorted?

237
00:11:32,290 --> 00:11:34,120
Is it possible that it's already sorted?

238
00:11:34,120 --> 00:11:35,680
Yes, that's quite probable.

239
00:11:35,680 --> 00:11:36,040
Right.

240
00:11:36,040 --> 00:11:36,970
Why is that so?

241
00:11:36,970 --> 00:11:40,510
Because we want to keep some data in a sorted manner.

242
00:11:40,510 --> 00:11:45,670
It's likely that it was already sorted, and probably we are trying to sort it again to ensure that

243
00:11:45,670 --> 00:11:46,300
it is sorted.

244
00:11:46,300 --> 00:11:46,630
Right.

245
00:11:46,630 --> 00:11:53,890
So it is likely that we encounter a scenario where we are given a sorted data and we are we may be asked

246
00:11:53,890 --> 00:11:54,400
to sort it.

247
00:11:54,400 --> 00:11:54,760
Right.

248
00:11:54,760 --> 00:12:00,940
So in that case, instead of picking the pivot as the first element or the last element, if you pick

249
00:12:00,940 --> 00:12:06,190
the pivot as the middle element, then we can avoid the worst case which we have seen.

250
00:12:06,190 --> 00:12:06,520
Right.

251
00:12:06,520 --> 00:12:12,970
If you are picking the pivot as the first element, we we always kept on calling it right and it kept

252
00:12:12,970 --> 00:12:14,800
on reducing only by one element, right.

253
00:12:14,800 --> 00:12:16,450
And we had to make n calls.

254
00:12:16,450 --> 00:12:20,920
So we can avoid that by picking the pivot as the middle element.

255
00:12:20,920 --> 00:12:23,110
And then the logic remains the same.

256
00:12:23,110 --> 00:12:23,470
Right.

257
00:12:23,470 --> 00:12:24,760
We can pick the middle element.

258
00:12:24,760 --> 00:12:27,430
And then we have these two two pointers.

259
00:12:27,430 --> 00:12:33,130
And we keep uh putting all the items which are less than the pivot to the left and greater than the

260
00:12:33,130 --> 00:12:33,790
pivot to the right.

261
00:12:33,790 --> 00:12:36,220
So that part of the logic remains the same.

262
00:12:36,220 --> 00:12:42,520
So the recommendation is pick the middle element as pivot or that's one possibility.

263
00:12:42,520 --> 00:12:46,120
Or you can or, or you can just put pick a random element.

264
00:12:46,420 --> 00:12:47,380
That is also possible.

265
00:12:47,380 --> 00:12:49,870
You can pick a random element as the pivot.

266
00:12:49,900 --> 00:12:56,830
Now if the again remember just to revise this o of n square happened when the list was sorted, it's

267
00:12:56,830 --> 00:13:00,520
probable that we may be asked to sort a sorted list, right?

268
00:13:00,520 --> 00:13:03,670
Because we want to ensure that that particular list is sorted.

269
00:13:03,670 --> 00:13:05,770
So to avoid O of n square.

270
00:13:05,770 --> 00:13:10,810
In that case, either pick the middle element as pivot or pick a random element as pivot.

271
00:13:10,810 --> 00:13:11,350
All right.

272
00:13:11,350 --> 00:13:13,960
So so far we have covered these two points.

273
00:13:13,960 --> 00:13:16,120
We have understood how quicksort works right.

274
00:13:16,120 --> 00:13:19,390
We pick a pivot and we identify its correct index.

275
00:13:19,390 --> 00:13:22,930
And then we move all items less than it to the left.

276
00:13:22,930 --> 00:13:26,320
And this is the pivot and all items greater than it to the right.

277
00:13:26,320 --> 00:13:30,130
And then we recursively call the quicksort right on these two parts.

278
00:13:30,130 --> 00:13:31,180
And we keep doing that.

279
00:13:31,180 --> 00:13:38,890
And we have seen the time complexity which is O of n log n average and best case and O of n square in

280
00:13:38,890 --> 00:13:40,090
the case of the worst case.

281
00:13:40,090 --> 00:13:42,610
And we have seen to avoid the worst case.

282
00:13:42,610 --> 00:13:44,710
And that happens in the case of sorted data.

283
00:13:44,710 --> 00:13:50,530
To avoid it, try to pick the middle element as the pivot, or pick a random element as the pivot.

284
00:13:50,530 --> 00:13:56,830
Now let's go ahead and discuss the space complexity of the quicksort, and let's make some tweaks to

285
00:13:56,830 --> 00:13:57,610
optimize it.