Short notes on Quicksort time complexity
- Quicksort is a divide and conquers type algorithm.
- There are two partitioning approaches for quicksort. One is the "Lomuto partition scheme" and another one is the "Hoare partition scheme".
- The space complexity of quicksort depends on the version chosen for the implementation.
- In-place partitioning technique, O(1) is required for space.
Time Complexity of Quick Sort
The number f(n) of comparisons necessary to sort n items is typically used to calculate the running time of a sorting algorithm. The quicksort algorithm, which has several variants, has been intensively researched. In general, the method has a worst-case run time of order n2/2, but an overall average time of order n log n. The reason behind this is explained further below.
Calculating the time complexity of quicksort
When the list has already been sorted, the worst-case scenario happens for the quicksorting. The first element will then need n comparisons to identify that it is still in the first place. Moreover, the first sublist will be empty, whereas the second will include n - 1 element. Consequently, the second element will need n- 1 comparison to identify that it is still in second place. And so forth. As a result, there will be a total of
f(n) = n + ( n - 1) + . . . . . . . . . + 2 + 1 = { n ( n + 1) } /2 = n2/2 + O ( n ) = O ( n2 )
Notable that, the input is also responsible for the Big O n-square notation. It takes n-th numbers in an array for the input method.
for(i=0;i<n;i++)
{
scanf("%d", &numbers[i]);
}
Furthermore, there is a nested loop inside the main function of the quicksort implementation. Also, time complexity increases for the pivoting in the quicksort to divide the array into the left and right sides.
while(i<=j)
{
while(a[piv] < a[j] && piv < j)
{
j--;
}
}
A short review on "Quicksort time complexity"
Time Complexity:
Best-case performance O(n log n) (simple partition)
O(n) (three-way partition and equal keys)
Worst-case performance O (n2)
Average performance O(n log n)
Space Complexity:
Average-case space complexity O(n)
worst-case space complexity O(log n)
Read Similar Posts:
2. Runtime Reduction of a Linear Search
3. Insertion Sort Time Complexity