Welcome back.
So far we have understood how the quicksort works.
All right.
Now over here, before we go ahead and code our solution, let's look at the time complexity of the
quicksort.
And let's look at the best case and the worst case.
And we will try to think of a few recommendations to avoid the worst case as much as possible.
Now we have seen that the quicksort works by taking an element as pivot.
And then we find the correct position where that pivot element should be after the array is sorted.
And then we will recursively call the quicksort on the left side and the right side right.
Now let's say we are given an array of size n.
And let's say the pivot that we choose is the median.
The median is nothing but the middle element of the given array, right.
Now what will happen?
The left side and the right side of the array now will have almost n by two elements right.
Let's look at it over here.
Let's say this is the array.
Now we pick that the pivot is the median or the middle value.
So we fix the pivot over here because it's the middle value.
So its correct position after the array is sorted will be in the middle of the given array.
Right.
So we fix it over here.
Now we will have let's say this is one element.
This the total size was n elements.
Now over here we will have the remaining elements in these two sides will be n minus one right.
And half of it will be over here.
So over here we will have n minus one by two elements which is almost n by two elements.
Right.
So I'm just avoiding this.
Right.
And over here also we will have n by two elements.
All right.
Now let's say this happens again and again.
Let me just clear this up.
Let's say this happens again and again.
That is we always pick the pivot as the median.
All right.
So this part over here will again be subdivided subdivided into two parts of n by four and n by four.
And we are recursively calling the quicksort algorithm on these subarrays.
Right again over here.
Also we will be dividing it into n by four and n by four.
And this will keep going till the size of the array is one.
And again an array of size one is already sorted.
So it will return.
At this point it will no longer call the quicksort right.
So this will go on till we get the size of the array as one.
Now let's try to find out the depth of this tree.
Right.
So you can see over here we have n which is nothing but n divided by two to the power zero.
Remember two to the power zero is equal to one right x to the power zero is equal to one.
Like if you take two to the power zero that's one.
Any any number.
If you just raise it to the power zero you will get one as the value.
All right.
So that was just a side note.
So over here the size is n.
Let's we are trying to make a pattern of this.
So n is nothing but two I can write n as n by one right.
And n by one is nothing but n by two to the power zero.
Right.
I'm just making this into a pattern.
So over here we have n divided by two to the power zero.
Over here we have n divided by two to the power one right.
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
two to the power two.
So there is a pattern right?
We have n divided by two to the power zero n divided by two to the power one n divided by two to the
power two.
And this goes on like that right till we get to one.
So this over here, I can write it as n divided by two to the power k right.
Because of the pattern.
Right.
So I can write this as n divided by two to the power k.
And that has to be equal to one, because we know we stop recursively calling the quicksort algorithm
when the size of the array is equal to one.
So n divided by two to the power k is equal to one, right.
So let me just clear this up.
So let's try to solve this.
Now, can we find the depth of the, uh, this this tree over here?
Right.
What's the depth over here?
N by two to the power k is equal to one.
So I can say two to the power k is equal to one.
Now if this is the case then k is nothing but log n right.
So we have seen that in the uh in the bigger video where we discussed about log n also.
Right.
So if two to the power k is equal to n then k is equal to log n.
Again.
Uh we have separately discussed this already.
So I'm not discussing this again over here.
So we have found that the number of levels in this case is equal to log n.
Right.
Okay.
And now when we look at each level so this is the number of levels.
Now when we look at each level for example this is one level right.
So over here in each level the partition algorithm will do n comparisons.
Right.
The partition algorithm will do n comparisons to find why.
Why will this do n comparisons to find the correct position of the pivot right.
The pivot has the correct index.
We have to place the pivot at the correct index and find that correct place, so that we can go ahead
and recursively call the quicksort.
And again divide n by two into n by four and n by four, which is left and right side of the pivot right.
The pivot element will be fixed.
And then the left side of that pivot will be an array of n by four size.
And the right side will be an array of n by four size.
So in each level, the partition algorithm will do n comparisons to find the pivot index and to place
the pivot at the right index.
So we are doing n comparisons in each level.
And how many levels do we have.
You can see that we have log n levels right.
In this case.
The case is where we always picked the pivot as the middle value.
So in this case there will be log n levels right.
So this is nothing but like a rectangle right.
We have in each level n comparisons and we have n levels.
So if you have a rectangle where the width is log n and the length is n, what is the area that would
be n into log n, right.
The same thing applies over here.
We have n, we have log n levels and in each level we are doing n comparisons.
So the total number of comparisons will be n into log n.
So the time complexity of the quicksort that we have discussed is O of n log n or order of n log n.
All right.
So that's the time complexity.
So we have seen that the time complexity of the quicksort is O of n log n.
But we got this with an assumption right.
The assumption was that the partitioning always happens in the middle.
So this was the assumption based on which we got the time complexity as o of n log n.
Now this is the best case scenario right now let's take a look at the worst case scenario so that we
can understand that this is the best case scenario.
It makes it easy if you look at the worst case scenario.
Now what is the worst case scenario?
If you always pick the pivot as the minimum or the maximum, then that would be the worst case.
Let's try to visualize this.
Let's say the given array is one, two, three, four, five.
And let's say we always pick the first value as the pivot.
All right.
So this array over here is already sorted.
So we are taking a sorted array.
And we always pick the first element as the pivot.
So in this case one is the pivot right.
So what will happen.
Partitioning will always happen at the beginning right.
So this is already in its correct place.
So when we call the quicksort on this array it will find this as the pivot.
It will fix this over here and it will return this index right.
So there is nothing on its left.
So in the right on its right it will it will call the quicksort on this part.
Let's take a look at it.
So we have seen that when we are getting a sorted array, the partitioning in this case always happens
at the beginning because we are taking the pivot at the beginning of the given array.
Right.
So let's visualize this.
So we have the array 12345.
So we call the quicksort on this array we fix the position of one and we return the pivot index.
Now we call the quicksort on this part 2345.
Right.
Again we fix.
So at this point one was fixed.
Now when we call it again we will fix two.
And again we will call the quicksort on 345.
We will fix the position of three.
So these three are fixed by now.
Again we will call the quicksort with four five.
And this will keep on happening till we get to the size of the array as one.
Right?
So over here let's say we have n elements.
So in this case we will do n operations or n comparisons.
And in the next level we will do n minus one comparisons.
In the next level we will do n minus two comparisons.
And this will go on till one.
Right.
So the total number of operations that we have to do over here is n plus n minus one plus n minus two
etc. up to one.
Right.
So we are adding these up.
This is n this is n minus one.
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.
This is nothing but n into n plus one by two right?
This is uh just sum of elements, right?
For example, if you have one plus two plus three plus four plus five.
So you can find this by doing n into n plus one by two which is five into five plus one which is six
by two.
Right.
So if you do that you will get the answer as 15.
Now let's sum it up.
One plus two is three.
Three plus three is six.
Six plus four is ten and ten plus five is 15.
Which is this 15 over here.
So one plus two plus three up to n.
That can be written as n into n plus one by two.
So that's the number of operations that we are getting in this case.
And this is what this is n square by two plus n by two.
Right.
If we simplify this now this is the dominating factor.
Right.
So we can neglect this and we can neglect the constant also.
So this over here will be an order of n square.
Right.
So the time complexity of the worst case of quicksort is O of n square which is not good.
Right.
So the best case we have seen is O of n log n.
And the worst case which we have seen over here is O of n square.
All right.
So we have seen that the time complexity of the quicksort is O of n log n, which is the best case.
And the worst case is O of n squared.
Now the average time complexity of the quicksort is also O of n log n.
And that involves a lot of maths to calculate it.
And you can check Wikipedia if you want if you're interested to look at the math.
But typically that's beyond the scope of any interview.
So we are not going to cover it over here.
So for the quicksort the best and average time complexity is O of n log n.
And the worst time complexity is O of n squared.
Now let's look at a few recommendations by which we could implement to try to avoid the worst case.
Right.
So this happened.
For this what you can do is always pick the middle element as pivot or the or you can pick a random
element as the pivot.
Now let's think of it right.
So we had a sorted array.
That's when the worst case happened.
Right.
And in case of a sorted array, if you are picking always the first element as pivot, or if you are
picking always the last element as pivot, we will get O of n square time complexity.
We've already seen that right.
So to avoid this we it's generally recommended that you pick the middle element as pivot.
Now why is that.
So it's easy.
Let's think of it in this way.
Is it probable that you will be given a sorted list?
Right.
This happens when you're given a sorted list.
So is it possible that the array which which we are asked to sort is already sorted, or the data which
is given to us, which is to be sorted?
Is it possible that it's already sorted?
Yes, that's quite probable.
Right.
Why is that so?
Because we want to keep some data in a sorted manner.
It's likely that it was already sorted, and probably we are trying to sort it again to ensure that
it is sorted.
Right.
So it is likely that we encounter a scenario where we are given a sorted data and we are we may be asked
to sort it.
Right.
So in that case, instead of picking the pivot as the first element or the last element, if you pick
the pivot as the middle element, then we can avoid the worst case which we have seen.
Right.
If you are picking the pivot as the first element, we we always kept on calling it right and it kept
on reducing only by one element, right.
And we had to make n calls.
So we can avoid that by picking the pivot as the middle element.
And then the logic remains the same.
Right.
We can pick the middle element.
And then we have these two two pointers.
And we keep uh putting all the items which are less than the pivot to the left and greater than the
pivot to the right.
So that part of the logic remains the same.
So the recommendation is pick the middle element as pivot or that's one possibility.
Or you can or, or you can just put pick a random element.
That is also possible.
You can pick a random element as the pivot.
Now if the again remember just to revise this o of n square happened when the list was sorted, it's
probable that we may be asked to sort a sorted list, right?
Because we want to ensure that that particular list is sorted.
So to avoid O of n square.
In that case, either pick the middle element as pivot or pick a random element as pivot.
All right.
So so far we have covered these two points.
We have understood how quicksort works right.
We pick a pivot and we identify its correct index.
And then we move all items less than it to the left.
And this is the pivot and all items greater than it to the right.
And then we recursively call the quicksort right on these two parts.
And we keep doing that.
And we have seen the time complexity which is O of n log n average and best case and O of n square in
the case of the worst case.
And we have seen to avoid the worst case.
And that happens in the case of sorted data.
To avoid it, try to pick the middle element as the pivot, or pick a random element as the pivot.
Now let's go ahead and discuss the space complexity of the quicksort, and let's make some tweaks to
optimize it.