Course contentsShow
← Computer Science
Lesson 605 of 2,87214. Heaps and Priority QueuesFree lesson

Heapsort Time Complexity Analysis

Analyzing why heapsort achieves O(n log n) worst-case time through building the heap and n extract-max operations.

Heapsort Time Complexity Analysis

You'll learn: Why heapsort consistently delivers O(n log n) performance in all cases, even the worst-case scenario.

Understanding the Two Phases

Heapsort consists of two distinct phases, and analyzing each reveals where the time complexity comes from.

Phase 1: Building the Max Heap
You've already learned that building a heap from an unsorted array takes O(n) time using the bottom-up construction method. This is a one-time cost at the beginning of the algorithm.

Phase 2: The Sorting Phase
After building the heap, you perform n extract-max operations. Each extract-max:

  • Removes the root (the maximum element)
  • Moves it to the end of the array
  • Calls heapify-down to restore the heap property

Since each heapify-down operation takes O(log n) time (bubbling down through the height of the heap), and you do this n times, Phase 2 costs O(n log n).

Why O(n log n) in All Cases

Combining both phases: O(n) + O(n log n) = O(n log n) overall.

What makes heapsort special is that this holds for best-case, average-case, and worst-case scenarios. Unlike quicksort (which can degrade to O(n²)), heapsort's performance doesn't depend on the input order. Whether the array is sorted, reverse-sorted, or random, you still build one heap and extract n elements.

Think of it like a factory assembly line: no matter what raw materials arrive, the process takes the same number of steps.

Key Takeaway:
Heapsort achieves O(n log n) worst-case time complexity because it builds a heap in O(n) time and performs n extract-max operations, each costing O(log n), giving guaranteed performance regardless of input.