Quick Sort Time Complexity for Best and Worst Cases
This class will try to understand Quick Sort Time Complexity for Best and Worst Cases.
We have already discussed the working mechanism and algorithm for quick sort in a straightforward way in our data structures course.
Quick Sort Time Complexity for Best and Worst Cases
Here we will discuss the scenario for the best and worst-case time complexities.
The image below is the scenarios for the worst-case time complexity.
The behavior of the quick sort is different compared to the other sorting techniques.
In quick sort, we will get the worst time complexities if the elements are already in the sorted order, the elements are in the reverse order, or if the values of all the elements are equal.
The image above shows all the scenarios for worst-case time complexity.
Now we will consider the first case where all the elements are in sorted order.
If we apply the partition algorithm to this arrangement, the pivot element five will be in its position, subdivided into the elements as T(n-1).
Again, if we apply the partition algorithm, the pivot element four will be in its position, and the elements to its left will be subdivided.
Again the subdivision has T(n-1) elements.
So, the recursive equation for this case is T(n) = T(n-1) + n.
n in the above equation represents the efficiency of the partition algorithm.
The solution for the above equation using the substitution method is provided in our previous class.
The efficiency of the quick sort for the above case is n2.
Similarly, the second and third cases will have the recursive equation T(n) = T(n-1) + n.
The time complexity of such scenarios will have a worst-case possibility of n2.
Now, we will consider the best-case scenario for the quick sort algorithm.
The best-case scenario is shown below.
In the best-case scenario, the elements are arranged so that the pivot element brought into its position will divide the array into two equal halves.
If the elements are arranged, then the recursive equation will be T(n) = 2T(n/2) + n.
The above recursive equation is the same as the recursive equation for the merge sort.
If we solve the recursive equation by substitution or masters method, the time complexity will be nlogn.
The worst-case time complexity of the quick sort is n2.
The best-case time complexity of the quick sort is nlogn.