Physics I / Complexity and efficiency basics
Practice question · Match the pairs

Match each everyday task to the growth rate of its work as nn 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
  • O(logn)O(\log n)
  • O(n2)O(n^{2})
  • O(n)O(n)
  • O(1)O(1)
Hints
  1. Ask: if the book doubled in size, how much would each task’s effort grow?
  2. Constant, halving, proportional, all-pairs, four fundamentally different responses to doubling.
Show the answer
  • Finding a page number in a book’s index O(logn)O(\log n)
  • Reading every page of a book once O(n)O(n)
  • Comparing every page with every other page O(n2)O(n^{2})
  • Opening the book’s front cover O(1)O(1)
Why

Big-O is the "what happens when n doubles" question: O(1)O(1) shrugs, O(logn)O(\log n) adds one step, O(n)O(n) doubles, O(n2)O(n^{2}) quadruples. Growth class, not raw speed, decides what is feasible at scale.

Read the lesson: Complexity and efficiency basics →

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