Course contentsShow
← Computer Science
Lesson 768 of 2,87218. Sorting AlgorithmsFree lesson

Best-Case Analysis: Balanced Partitions

Analyze quicksort's O(n log n) best-case performance when pivots consistently divide arrays evenly.

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:

  1. 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).

  2. 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.

  3. 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.