Practice question · Match the pairs
Match each complexity class to an operation that has it.
- Constant
- Logarithmic
- Linearithmic
- Quadratic
- Indexed access to one array element
- Two nested loops over the same data
- Binary search on sorted data
- Merge sort
Hints
- One class is achieved only by repeatedly discarding half the data.
- The best comparison-based sorting sits between linear and quadratic.
Show the answer
- Constant → Indexed access to one array element
- Logarithmic → Binary search on sorted data
- Linearithmic → Merge sort
- Quadratic → Two nested loops over the same data
Why
These four examples are the canonical ones, and they are worth memorising because almost every algorithm you meet resembles one of them. Merge sort's linearithmic cost is the best any comparison-based sort can achieve.
Practise Computational Complexity
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Computational Complexity
- Select every statement about big-O notation that is TRUE.
- Order these complexity classes from the slowest-growing to the fastest-growing.
- A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly…
- Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many…
- Binary search is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched…
- Complete the description of big-O notation.
- An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program…