Project ForgeThe number of elements that can be sorted in Θ(log n) time using heap sort is
- AΘ(1)
- BΘ(√log n)
- Θ(log n / log log n)
- DΘ(log n)
Explanation
Heap sort takes Θ(m log m) to sort m elements. We need the largest m such that m log m = Θ(log n). Try m = Θ(log n / log log n): then log m ≈ log(log n) − log(log log n) ≈ log log n (the second term is lower-order), so m·log m ≈ (log n / log log n)·(log log n) = log n — exactly matching. Checking m = Θ(√log n) instead: log m ≈ ½ log log n, so m log m ≈ √(log n)·½ log log n, and the ratio of this to log n is (log log n)/√(log n) → 0, i.e. it UNDERSHOOTS Θ(log n) — too small. So m = Θ(log n / log log n) is the correct answer.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.