Practice question · Put in order
Order these complexity classes from the slowest-growing to the fastest-growing.
- Quadratic
- Exponential
- Constant
- Linear
- Logarithmic
Hints
- Compare how each behaves as n gets very large, not on small inputs.
- One class does not grow at all; one doubles with every extra element.
Show the answer
- Constant
- Logarithmic
- Linear
- Quadratic
- Exponential
Why
Constant, logarithmic, linear, quadratic, exponential is the standard ladder. The gaps are enormous: at n = 1,000,000 the linear algorithm does a million steps and the quadratic a trillion, while the exponential one is hopeless well before n = 100.
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.
- Match each complexity class to an operation that has it.
- 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…