Now that you have seen the pseudocode for QuickSort and also seen its Java implementation, it is now time to know about the time complexity of the QuickSort algorithm. Let us find out in the coming video how Quicksort fares out when it comes to time complexity.

In the first video, you are going to take a look at the partition function and how much time does it take for that function to execute. Then in the next videos, you are going to see what is the time complexity in the best and the worst case of the QuickSort algorithm.

$$/$$

Video Transcript

Now let us take a look at the time complexity of the Quicksought algorithm. So here my Quicksort uses a partition function. So let us first see what is the time complexity of our partition function. So here in my partition function, in the first two steps I am just calculating and assigning values to the variables pivot and p. There is no extra computation involved and I am just assigning some particular values to these variables. So these two steps are going to take a constant amount of time. Moreover, if you notice here in the last two steps also I am just exchanging the values of A of p and A of end, which is independent of the size of my input array. Moreover, in the last step when I'm returning p, this also does not involve any dependency on the number of elements in the array. So both these operations are also running in constant amount of time. Now, let us look at this for loop. Now, here the inside operations which are happening in this if loop, they are also of constant time since

we are only swapping these two elements and changing the value of p. So this particular steps take a constant amount of time. But if you notice here carefully, this is enclosed inside a for loop and this for loop runs its iterator I from start till the end, which means that I is dependent on N. That is, if I have eight elements, this for loop is going to run eight times. And if I have 1 million elements, this for loop is going to run 1 million times. So this means that this for loop is dependent on N. So this gives me that this entire procedure is of the order of N. That is for running this for loop it would require order N amount of time. So now, all of these operations which are occurring in a constant amount of time are independent of the number of elements in our array. That is, it does not really matter if my array has eight elements or 1 million elements, because this Pivot and p assignment steps are going to take a constant amount of time and same is the case with these two steps.

However, this for loop clearly depends on N. So what is the total time complexity of this partition operation? Well, the total time complexity of this partition operation will be C plus N plus C. That is this partition operation is going to take C for these two steps and N times for when the for loop is going to run and C for these two operations. So this gives me N plus some constant C prime. So basically in the conclusion, you should remember that this entire partition function occurs in order N amount of time.

Video Recap

Quicksort algorithm uses a partition function
Partition function time complexity analysis
First two steps in partition function assign values to pivot and p, no extra computation involved
Last two steps involve exchanging values of A of p and A of end, which is independent of input array size
Returning p also does not involve any dependency on the number of elements in the array
Inside operations in the for loop are also of constant time since only swapping two elements and changing value of p
For loop runs from start till end and is dependent on N
Entire procedure is of order N, dependent on N
Partition operation time complexity is C + N + C
Partition operation occurs in order N amount of time
Total time complexity of partition operation is N + some constant C prime

Now that you have seen the time complexity of the Partition function of Quicksort, we will now learn about how much time does it take for the actual Quick Sort algorithm to run. In the next video, you are going to see the time complexity of Quick Sort in the worst case.

$$/$$

Till now you have seen the worst case time complexity of the Quick Sort algorithm. In the coming video, we will see what is the time complexity of Quick Sort in the best case.

$$/$$

Great! Now we have successfully derived the time complexity expressions of the best and the worst case of the Quick Sort algorithm. Aishwarya will now summarise the time complexities of the Quick Sort in the coming video, comparing the best, worst and average case time complexities of Quick Sort.

$$/$$

Quicksort also comes out to have a time complexity of O(N log N). However, in the worst case, its time complexity is O(N $^{2}$ ). Despite this, most of the cases we encounter are closer to the average case and not the worst or best cases. So, again it is one of the most widely used algorithms because of its time complexity.

Here is the link for time complexity analysis of Quicksort in detail.

Please refer to the link below on how to chose a random pivot.

Random Pivot

That was interesting, wasn’t it? In the next section, you are going to see through a game of cards how Quick Sort works.