QuickSort: Time Complexity

In this assignment, we will discuss the time complexity of the Quicksort algorithm.

In Quicksort, the time complexity is influenced by two main factors: the partitioning step and the recursion step.

Partitioning Step

During the partitioning step, Quicksort scans the array once and partitions it based on the chosen pivot element. The partitioning process involves rearranging the elements such that elements smaller than the pivot are placed to the left, and elements greater than the pivot are placed to the right. On average, this process takes linear time, O(N), where N is the number of elements in the array. The exact implementation details of partitioning may vary, but the overall time complexity remains linear.

Recursive Step

After partitioning, as we have seen, Quicksort recursively applies the partitioning process to the subarrays created. This recursive process repeatedly divides the array into smaller parts until each subarray contains either zero or one element, which are already considered sorted. The recursion occurs on average log N times because each recursive call typically divides the array into two roughly equal-sized subarrays.

Combining the Partitioning and Recursion Steps

Since the partitioning step takes linear time, and the recursion occurs logarithmically, we can multiply these complexities together. As a result, the overall average-case time complexity of Quicksort is expressed as O(N log N), where N is the number of elements in the array.

It is important to note that the O(N log N) time complexity represents the average-case scenario, which occurs when the input array is randomly ordered or has no specific patterns. In this case, Quicksort performs efficiently and sorts the array effectively.

However, in the worst-case scenario, as we have seen in previous assignments, the time complexity of Quicksort can degrade to O(N^2). This occurs when the input array is already sorted or nearly sorted, and a poor pivot selection strategy is used. For example, always choosing the first or last element as the pivot can lead to highly imbalanced partitions. As a result, the recursion tree becomes skewed, and each level of the tree only reduces the problem size by one element. This significantly increases the number of comparisons and swaps required.