Question

Show that the best-case running time of quick-sort on a sequence of size \(n\) with distinct elements is \(O(n \log n)\).

Short answer

The best-case running time for quick sort on an array of size \(n\) with distinct elements is \(O(n \log n)\).

Step-by-step solution

Understanding Quick Sort

Quick sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Best Case Scenario

The best-case scenario for quick-sort occurs when the pivot element always splits the array into two equal (or nearly equal) halves. This results in the most balanced partitioning possible.

Recurrence Relation

In the best case, each partition step splits the array into two halves of roughly equal size. The recurrence relation for the best-case time complexity can be written as: \[ T(n) = 2T\bigg(\frac{n}{2}\bigg) + O(n) \]The term \(2T\bigg(\frac{n}{2}\bigg)\) represents the time complexity of sorting the two sub-arrays, and the term \(O(n)\) represents the time complexity of partitioning the array.

Solving the Recurrence Relation

To solve the recurrence relation, apply the Master Theorem for divide-and-conquer recurrences. For \(T(n) = aT\big(\frac{n}{b}\big) + f(n)\), where in our case, \(a = 2\), \(b = 2\), and \(f(n) = O(n)\). According to the Master Theorem: - If \(f(n) = O(n^c)\) where \(c = \log_b(a)\), then \(T(n) = O(n^c \log n)\).

Applying the Master Theorem

Here, \(a = 2\) and \(b = 2\), so \(\log_b(a) = \log_2(2) = 1\). Since \(f(n) = O(n)\), it follows that in the best case, \(T(n) = O(n \log n)\).

Conclusion

Hence, the best-case running time for quick sort on an array of size \(n\) with distinct elements is \(O(n \log n)\).

Key concepts

quick sort algorithm

The quick sort algorithm is a fundamental sorting technique in computer science. It's classified as a 'divide-and-conquer' algorithm. Here's how it works:
First, a 'pivot' element is selected from the array. The pivot can be any element, but common choices include the first element, the last element, or a random element. Once the pivot is chosen, the array is partitioned into two sub-arrays:

• Elements less than the pivot.
• Elements greater than the pivot.

The pivot element itself is then considered 'in place.'
The algorithm recursively applies this process to the sub-arrays. This way, larger sets are broken down into smaller, more manageable sets. The base case of this recursion is arrays of size zero or one, which are already sorted.
This method ensures that the array gets sorted with a series of steps that handle smaller and smaller arrays. The quick sort algorithm has average and best-case time complexities of \(O(n \log n)\).

divide-and-conquer

Divide-and-conquer is a crucial algorithm design paradigm used in many algorithms, including quick sort. The basic idea is to break a problem down into smaller, easier to solve sub-problems, and then combine solutions to these sub-problems to solve the original problem.
Here's how it applies to the quick sort:

• Divide: The array is divided into two sub-arrays based on the pivot.
• Conquer: The quick sort algorithm is recursively used to sort the sub-arrays.
• Combine: Since the pivot is already in its correct position, combining the sub-arrays essentially means merging them back.

This approach helps efficiently reduce the problem size at each step, employing recursion to handle the complex task of sorting large arrays. It is the elegance of the divide-and-conquer method that ensures sorting happens efficiently, especially in the best and average scenarios.

recurrence relation

Recurrence relations are mathematical equations that represent the time complexity of recursive algorithms. They express the overall running time of an algorithm based on its performance on smaller inputs.
For quick sort, in the best-case scenario where the pivot splits the array into two equal halves, the recurrence relation is:
\[ T(n) = 2T\left( \frac{n}{2} \right) + O(n) \]
Here's the breakdown:

• \(2T\left( \frac{n}{2} \right)\) signifies the time taken to recursively sort the two sub-arrays.
• \(O(n)\) represents the time taken to partition the array around the pivot.

In simpler terms, we are solving two sub-problems of half the array size and adding the linear time complexity for partitioning. This relation captures the essence of how the overall complexity is constructed from sorting smaller and smaller sub-arrays.

Master Theorem

The Master Theorem provides a straightforward way to solve recurrence relations of the form:
\[ T(n) = aT\left( \frac{n}{b} \right) + f(n) \]
For quick sort, our recurrence relation is:
\[ T(n) = 2T\left( \frac{n}{2} \right) + O(n) \]
Here:

• \(a = 2\) (number of sub-arrays)
• \(b = 2\) (each sub-array is half the size of the original)
• \(f(n) = O(n)\) (linear time for partitioning)

To apply the Master Theorem, we calculate:
\[ c = \log_b{a} = \log_2{2} = 1 \]
The theorem states that:
- If \(f(n) = O(n^c)\), and in our case, \(c = 1\), then \(T(n) = O(n^c \log{n})\). Since \(f(n) = O(n)\) fits this condition perfectly, we conclude that:
\( T(n) = O(n \log{n}) \)
Therefore, the Master Theorem confirms our earlier calculations, indicating that the best-case time complexity of quick sort is \(O(n \log n)\).