Worst-case Complexity of Heap Sort MCQ: Correct Option | AI Research

Worst-case Complexity of Heap Sort (MCQ: Correct Option)

Verified Sources

Sep 13, 2026

Heap sort has a worst-case (and also average-case) time complexity of $O(n\log n)$ because it performs $n$ extraction steps, each involving a heap adjustment that costs $O(\log n)$ . Therefore, the correct answer is (iii) $O(n\log n)$ .

Key idea: after building a max-heap, each delete/extract-max requires “sift-down” (heapify-down) which traverses at most the height of the heap, i.e., $O(\log n)$ . Repeating this for $n$ elements yields $O(n\log n)$ .

Keywords: Heap sort Max-heap Heapify-down Time complexity

Heap Sort Complexity (Build Heap + Extract + Sift Down)

Why heap sort is $O(n\log n)$ in the worst case

After the initial Build heap step, heap sort performs $n-1$ extractions. Each extraction consists of:

Swap the heap root with the last element.
Restore heap order using heapify-down.

The heap height is $O(\log n)$ for a binary heap, so the sift-down per extraction is $O(\log n)$ even in the worst case (when the element moved must travel from root to a leaf).

Thus, worst-case time:

T(n)=O(n)+n\cdot O(\log n)=O(n\log n).

Keywords: Binary heap Worst case Asymptotic analysis Root extraction

Heap sort runtime breakdown

1
Step 1
Convert the array into a valid heap (typically via bottom-up heapify). This costs $O(n)$ in standard analysis.
2
Step 2
For $k=n$ down to 2: swap the root with the last unsorted element and reduce the heap size.
3
Step 3
Run heapify-down from the root; the element may move down at most the heap height, costing $O(\log n)$ .
4
Step 4
Total time is $O(n) + (n-1)\cdot O(\log n)=O(n\log n)$ , so the worst case is $O(n\log n)$ .

Pro Tip

When options include $O(\log n)$ or $O(n)$ , remember heap sort must do $n$ extractions, and each extraction includes an $O(\log n)$ heap adjustment.

Common confusion

The $O(n)$ part comes from building the heap, but the dominating cost is the $n$ times heapify-down: $n\cdot O(\log n)=O(n\log n)$ .

Heap sort worst-case runtime components

Dominating term determines the final asymptotic complexity.

Heap sort lifecycle (high-level)

Heap Construction

Step A

Bottom-up heapify makes the array a heap."

Repeated Extraction

Step B

Swap max/min at the root to its final position."

Sift Down (Re-heapify)

Step C

Restore heap property; each sift-down takes $O(\log n)$ . "

MCQ Answer & Rationale

Knowledge Check

Question 1 of 3

Q1Single choice

What is the worst-case time complexity of heap sort?

(i) $O(\log n)$

(ii) $O(n^2)$

(iii) $O(n \log n)$

(iv) $O(n)$

Explore Related Topics

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size  $n$ , explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

Best case: $T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I)$ , the minimum time over all inputs of size  $n$ .
Worst case: $T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I)$ , giving a guaranteed upper bound.
Average case: $T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I)$ , requiring an explicit input probability model.
Linear search illustrates the three cases: $\Theta(1)$ best, $\Theta(n)$ worst, and $\Theta(n)$ average (expected $\frac{n+1}{2}$ comparisons).
Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.

Applications of the Queue Data Structure (MCQ: Which option is correct?)

Browse all research articles