Practice question · Multiple choice
An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program to use?
Hints
- Compare 100·n log n against 2·n² at n = 10. Which is larger?
- Ask what big-O deliberately throws away.
Show the answer
D. Because big-O describes growth and discards constant factors.
Why
Big-O discards constants and lower-order terms to answer one question cleanly, and those discarded parts decide small cases: at n = 10, 100·n log n is about 3300 units against 2n²'s 200. Production sorts are hybrids for exactly this reason, switching to insertion sort below 10 to 20 elements. The mistake is treating an answer about growth as an answer about speed.
Practise Computational Complexity
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Computational Complexity
- Select every statement about big-O notation that is TRUE.
- Match each complexity class to an operation that has it.
- Order these complexity classes from the slowest-growing to the fastest-growing.
- A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly…
- Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many…
- Binary search is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched…
- Complete the description of big-O notation.