ITPEC FE Subject A October 2024 Question 3
ITPEC FE Subject A October 2024 — Question 3 of 60
Heapsort Complexity — identify the time complexity of Heapsort.
Heapsort has two phases:
- Build heap from array → O(n)
- Extract max n times, each requiring sift-down → n × O(log n)
Total: O(n) + O(n log n) = O(n log n)
Why not others:
- (a) O(log n) — complexity of a single sift-down, not the full sort
- (b) O(n) — only the heap-building phase
- (c) O(n²) — typical of Bubble Sort, Selection Sort, Insertion Sort
Key rule: Heapsort, Merge Sort, and Quick Sort (average) all run in O(n log n).
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.