Best-Case Analysis: Balanced Partitions
What You'll Learn
You'll discover why quicksort achieves O(n log n) performance in its best case—when the pivot consistently splits the array into two equal halves.
The Ideal Scenario
In the best case, quicksort's partition operation divides the array perfectly in half every time. Imagine cutting a deck of 8 cards: first into two piles of 4, then each pile into two piles of 2, then each pair into singles. You only needed 3 levels of cuts to reach individual cards.
Why O(n log n)?
When partitions are balanced:
-
Depth of recursion: Each level cuts the problem size in half, so you need log₂ n levels to reduce n elements down to size 1 (just like our card deck: 8 → 4 → 2 → 1 took log₂ 8 = 3 steps).
-
Work per level: At each recursion level, every element gets examined once during partitioning. That's O(n) work per level, regardless of how the elements are distributed.
-
Total work: O(n) work across O(log n) levels = O(n log n) total time.
The Intuition
Think of a balanced binary tree: if you have n elements and keep splitting evenly, the tree's height is log n. Quicksort with balanced partitions follows this same structure—each partition creates a tree node, and traversing all nodes (doing the partition work) takes linear time at each tree level.
Key Takeaway: Quicksort achieves O(n log n) best-case performance when pivots consistently divide the array into roughly equal halves, resulting in logarithmic recursion depth with linear work per level.