Practice question · True or false
Big-O notation compares how algorithms scale, so an algorithm always runs faster than an one on the same input.
Hints
- Ask what big-O deliberately throws away.
- Constant factors and the size of n both survive in the real runtime.
Show the answer
False
Why
False. Big-O describes growth as n tends to infinity and discards constant factors, so a heavily-optimised routine can beat a constant-heavy one at every n a real program ever sees. The crossover point is a measurement, not something the notation tells you.
Practise Complexity and Performance Trade-offs
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 Complexity and Performance Trade-offs
- Two algorithms are timed on one machine: the O(n) one takes 3 seconds at n = 1000 and the O(n²) one takes 1…
- An O(n log n) sort applied to a nearly-sorted list can be slower than an O(n²) insertion sort on the same…
- Order these growth classes from the slowest-growing to the fastest-growing as n becomes large.
- A team spends a week optimising a function that accounts for 2% of runtime. What did they get, and what is…