Quicksort — Notes & Complexity
Source: Quicksort — Divide & Conquer · CS 161
Algorithm idea
CS 161- Choose pivot → partition → recurse on both halves
- In-place, not stable
Complexity table
CS 161| Case | Time | Space |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
Recurrence
CS 161- T(n) = 2·T(n/2) + Θ(n) ⇒ Case 2 ⇒ Θ(n log n)
Interview cards
CS 161- Q: Why use a randomized pivot? A: to avoid Θ(n²) worst case on adversarial or sorted input.



