Practice question · Multiple choice
Two algorithms are timed on one machine: the O(n) one takes 3 seconds at n = 1000 and the O(n²) one takes 1 second. What can you predict about n = 100,000, and what can you not?
Hints
- n grows by a factor of 100. What does that do to each algorithm's work?
- Ask which parts of the real running time the growth class does not describe.
Show the answer
A. That a crossover exists and roughly where, but not the exact times.
Why
Scaling n by 100 multiplies linear work by 100 and quadratic by 10,000, so 3 seconds becomes 300 and 1 second becomes nearly three hours, the initial advantage is irrelevant at scale. What growth classes cannot give you is the actual numbers, and at large n the quadratic may exceed memory and start swapping, at which point the extrapolation understates the disaster.
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
- 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…
- Big-O notation compares how algorithms scale, so an O(nlog n) algorithm always runs faster than an O(n²) one…