ITPEC FE Subject A October 2024 Question 3
Which of the following is the computational complexity of the Heapsort algorithm? Here, n is the number of elements to be sorted, and all comparisons, swaps, and other needed operations can proceed in constant time.
Explanation
O(n log n) — Heapsort builds a heap once, then removes the maximum n times at a cost of log n each.
- •Build a heap from the array: O(n)
- •Repeat n times: swap the root (the maximum) to the end of the array and sift the new root down a tree of height about log n: n × O(log n)
Total O(n) + O(n log n) = O(n log n), and this bound holds in the worst case, not only on average.
Answer (d)
Why not others:
- •(a) O(log n) — the cost of one sift-down, not of sorting all the elements
- •(b) O(n) — the cost of the heap-building phase alone; a comparison sort cannot sort n arbitrary elements in linear time
- •(c) O(n²) — the order of simple sorts such as bubble, selection and insertion sort, and of quicksort's worst case
Key rule: Heapsort and merge sort are O(n log n) even in the worst case; quicksort is O(n log n) on average but O(n2) at worst.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.