Practice question · Multiple choice
An algorithm can beat an one on real data. How is that consistent with the complexity classes?
Hints
- Ask what big-O deliberately throws away.
- Compare with at .
Show the answer
B. Because big-O describes growth and discards constants
Why
Asymptotic notation is about the limit, and real inputs are finite. Timsort and introsort both exploit this by switching algorithms below a size threshold.
Practise Complexity and efficiency basics
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Complexity and efficiency basics
- O(n²) simplifies to O(n) in Big-O notation, since constant factors are dropped.
- Two nested loops each running n times give O(n²). Why does the analysis not simply add the two loops?
- Match each everyday task to the growth rate of its work as n grows.
- An O(n²) simulation takes 2 seconds for n = 1000 particles. Predict its runtime for n = 5000, in seconds.