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

Heapsort Time Complexity Analysis

Analyzing the O(n log n) worst-case, average-case, and best-case time complexity of heapsort.

Heapsort Time Complexity Analysis

You'll learn: Why heapsort consistently runs in O(n log n) time regardless of input order.

The Two Phases of Heapsort

Heapsort performs two distinct operations: building the initial heap and repeatedly extracting the maximum element. Understanding each phase's cost reveals the overall complexity.

Phase 1: Building the Heap

Converting an unsorted array into a max-heap takes O(n) time. This might seem counterintuitive since we have n elements, but the "heapify-down" operations on upper levels affect fewer elements. The mathematical analysis shows most elements are near the bottom of the heap and require minimal work.

Phase 2: Extraction Loop

After building the heap, we extract the maximum element n times. Each extraction:

  • Swaps the root with the last element: O(1)
  • Performs heapify-down from the root: O(log n)

Since we do this n times, the extraction phase costs n × O(log n) = O(n log n).

All Cases Are O(n log n)

Best-case: Even if the array is already sorted, heapsort still builds the heap (O(n)) and performs all n extractions with heapify operations (O(n log n)). Total: O(n log n).

Average-case: Random data requires the same heap-building and extraction steps. Total: O(n log n).

Worst-case: No input arrangement can make the heap operations fundamentally worse. Each heapify-down is bounded by the tree height (log n). Total: O(n log n).

Why This Matters

Unlike quicksort, heapsort has no worst-case quadratic behavior. The logarithmic factor comes directly from the heap's tree height, which depends only on the number of elements, not their arrangement.

Key Takeaway: Heapsort guarantees O(n log n) time complexity in all cases—best, average, and worst—making it predictable but typically slower than well-implemented quicksort in practice due to cache behavior.