Practice question · Multiple choice
An O(n log n) sort loses to an O(n²) insertion sort on a 20-element array, and every production sort library exploits this. What are they doing?
Hints
- Big-O throws something away. Ask what, and when it matters.
- Compare 100·n log n with 2n² at n = 20.
Show the answer
B. Switching to insertion sort below a threshold, where constants win
Why
Constants are exactly what the notation discards, and at small n they dominate, which is why Timsort and libstdc++ both fall back to insertion sort under about 16 to 32 elements. Big-O answers a question about scaling, and using it to answer a question about speed is the error.
Practise What Makes an Algorithm Good
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on What Makes an Algorithm Good
- The lesson says an algorithm must be finite and definite. Select every description that violates at least one…
- Match each quality or property to its meaning.
- Order the recommended design workflow, which puts correctness before speed.
- A set of instructions counts as a genuine algorithm only if it is finite (it always stops) and definite…