Understanding Quicksort Worst Case Running Time

Quicksort is a popular sorting algorithm known for its efficiency in practice. However, its performance varies significantly depending on the choice of the pivot element.

Quicksort Algorithm Overview

Quicksort works by:

• Selecting a 'pivot' element from the array.
• Partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
• Recursively sorting the two sub-arrays.

The base case of the recursion is arrays of size zero or one, which are already sorted.

Analyzing Quicksort Time Complexity

The time complexity of Quicksort depends on how balanced the partitioning is. Let n be the number of elements in the array (corresponding to 'x' in the options).

• Best Case: The pivot always divides the array into two roughly equal halves. The recurrence relation is $T(n) = 2T(n/2) + \Theta(n)$. Solving this gives a time complexity of $\Theta(n \log n)$.
• Average Case: On average, the partitioning is reasonably balanced. The average case time complexity is also $\Theta(n \log n)$.
• Worst Case: This occurs when the pivot selection consistently leads to highly unbalanced partitions.

Quicksort Worst Case Explained

The worst-case scenario happens when the pivot element is always the smallest or the largest element in the current sub-array. This results in one partition with n-1 elements and the other with 0 elements.

Let's look at the recurrence relation for the worst case:

$T(n) = T(n-1) + T(0) + \Theta(n)$

Here:

• $T(n)$ is the time to sort an array of size n.
• $T(n-1)$ is the time to sort the sub-array containing n-1 elements.
• $T(0)$ is the time to sort the empty sub-array (which is constant, i.e., $\Theta(1)$).
• $\Theta(n)$ is the time taken for the partitioning process for an array of size n.

Since $T(0)$ is negligible for large n, the recurrence simplifies to:

$T(n) = T(n-1) + \Theta(n)$

Solving the Worst-Case Recurrence

We can expand this recurrence relation:

• $T(n) = T(n-1) + cn$ (where $c$ is a constant)
• $T(n-1) = T(n-2) + c(n-1)$
• $T(n-2) = T(n-3) + c(n-2)$
• ...
• $T(2) = T(1) + c(2)$

Substituting back:

$T(n) = (T(n-2) + c(n-1)) + cn = T(n-2) + c(n-1) + cn$

$T(n) = (T(n-3) + c(n-2)) + c(n-1) + cn = T(n-3) + c(n-2) + c(n-1) + cn$

Continuing this pattern down to $T(1)$ (which is $\Theta(1)$):

$T(n) = T(1) + c(2) + c(3) + \dots + c(n-1) + cn$

$T(n) = \Theta(1) + c \sum_{i=2}^{n} i$

The sum $\sum_{i=2}^{n} i$ is approximately $\sum_{i=1}^{n} i - 1 = \frac{n(n+1)}{2} - 1$, which is $\Theta(n^2)$.

Therefore, the worst-case time complexity is $\Theta(n^2)$.

Comparing this with the given options, where 'x' represents 'n':

The worst case running time of quicksort algorithm is $\Theta(n^2)$.

Revision Table: Quicksort Complexity

Additional Information on Quicksort Performance

While the worst-case complexity of Quicksort is $\Theta(n^2)$, it is rarely encountered in practice with good pivot selection strategies.

• Pivot Selection: Common strategies to avoid the worst case include:
  • Choosing a random element as the pivot.
  • Choosing the median of three elements (first, middle, and last).
  Using these strategies makes the worst case highly improbable for random input data, leading to the average-case $\Theta(n \log n)$ performance becoming the typical observed behavior.
• Space Complexity: The space complexity of Quicksort is typically $\Theta(\log n)$ in the average case due to the recursion stack depth. In the worst case (unbalanced partitions), the recursion depth can be $\Theta(n)$, leading to a space complexity of $\Theta(n)$. This can be improved to $\Theta(\log n)$ worst case by using an iterative approach or tail recursion optimization for the larger sub-array.
• In-place Sort: Quicksort is generally considered an in-place sorting algorithm because the partitioning step requires only a small amount of auxiliary space (for the pivot and possibly a few pointers).

Despite its potential worst case, Quicksort is often faster than other $\Theta(n \log n)$ algorithms like Merge Sort for many practical inputs due to its smaller constant factors and cache efficiency.