ITPEC FE Morning October 2018 Question 4
ITPEC FE Morning October 2018 — Question 4 of 80
Heapsort Time Complexity — know that Heapsort always runs in O(n log n).
Heapsort works in two phases:
- Build a max-heap from the input array — this takes O(n) time.
- Repeatedly extract the maximum element and restore the heap property (heapify). Each extraction does a "sift-down" through the heap's height, which is log n. Doing this for all n elements costs O(n log n).
Total: O(n) + O(n log n) = O(n log n).
A key property of Heapsort is that its time complexity is O(n log n) in all cases — best, average, and worst — unlike Quicksort, which degrades to O(n²) in the worst case.
Why not others:
- (a) O(log n) — this is the cost of a single heapify operation, not the entire sort
- (b) O(n) — this is the cost of building the heap, not sorting
- (c) O(n²) — this is the worst case for Bubble Sort or Selection Sort, not Heapsort
Key rule: Heapsort = O(n log n) always. It combines heap construction O(n) with n extractions at O(log n) each.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
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.