Practice question · Match the pairs
Match each everyday task to the growth rate of its work as grows.
- Finding a page number in a book’s index
- Reading every page of a book once
- Comparing every page with every other page
- Opening the book’s front cover
Hints
- Ask: if the book doubled in size, how much would each task’s effort grow?
- Constant, halving, proportional, all-pairs, four fundamentally different responses to doubling.
Show the answer
- Finding a page number in a book’s index →
- Reading every page of a book once →
- Comparing every page with every other page →
- Opening the book’s front cover →
Why
Big-O is the "what happens when n doubles" question: shrugs, adds one step, doubles, quadruples. Growth class, not raw speed, decides what is feasible at scale.
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.
- An O(n²) algorithm can beat an O(nlog n) one on real data. How is that consistent with the complexity classes?
- Two nested loops each running n times give O(n²). Why does the analysis not simply add the two loops?
- An O(n²) simulation takes 2 seconds for n = 1000 particles. Predict its runtime for n = 5000, in seconds.