16.1.5. Average Case Complexity

Try these first

1. 1.

   What is the average case time complexity of Quicksort?

   Hint

   Think about how the algorithm performs across many typical inputs.

2. 2.

   How does Quicksort partition an array?

   Hint

   Remember the role of the pivot in dividing the array.

3. 3.

   What is the worst-case time complexity of Quicksort?

   • O(n log n)
   • O(n²)
   • O(n)

   Hint

   Reflect on cases where the pivot choice leads to unbalanced splits.

4. 4.

   Average-case performance of Quicksort is O(n log n). True or False?

   • True
   • False

   Hint

   Think about how it performs on most random inputs.

5. 5.

   Design an example input for Quicksort that results in the worst-case performance. Explain your reasoning.

   Hint

   Consider how the partitioning impacts the subsequent recursive calls.

6. 6.

   Transform the provided Quicksort pseudocode into an iterative form using a stack. Explain how stack operations mirror recursive calls.

   Hint

   Trace through the recursive calls to see how they'd translate into managing state on a stack.