Where does O(n log n) come from?
“Explain what O(n log n) means and where the log factor typically comes from.”
What this tests
- Whether the candidate can explain a log factor mechanically, not just recite it.
- Whether they know the three common sources: halving, balanced-tree operations, and
nbinary searches. - Sense of scale: how
n log ncompares tonandn^2for realistic inputs.
Strong answer
A log factor appears whenever something is halved repeatedly. log_2 n is the number of times you can halve n before reaching 1 — for 10^6 that is about 20. O(n log n) therefore means "linear work, done about 20 times" for a million elements, which is why it is treated as nearly linear in practice.
Three sources cover almost every case. Divide and conquer: Merge Sort does O(n) merging at each of log n levels. Per-element tree or heap operations: inserting n items into a Binary Heap or balanced BST is n operations of O(log n) each — Heap Sort and Dijkstra's Algorithm get their log this way. `n` binary searches: sort once, then do a Binary Search for each of n queries.
A strong candidate adds the comparison-sorting lower bound (Ω(n log n) comparisons, from log_2(n!)) and the sense of scale: for n = 10^5, n^2 = 10^{10} is too slow, n log n ≈ 1.7 × 10^6 is trivial.
Green flags · Red flags
- Explains
log nas "number of halvings" with a concrete number (log_2 10^6 ≈ 20). - Names all three sources with an example each.
- Knows comparison sorting cannot beat
n log nand why counting sort escapes the bound. - Compares magnitudes for a real
n.
- Cannot say why merge sort is
n log nbeyond "it just is". - Thinks
O(n log n)is much closer toO(n^2)than toO(n). - Confuses
log nwithn / 2.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
O(n log n) on average but O(n^2) worst case?O(n + k) if sorting is Ω(n log n)?O(n log k) and when do you see it?