Practice question · Put in order
Order these growth classes from the slowest-growing to the fastest-growing as n becomes large.
- Linear
- Logarithmic
- Exponential
- Linearithmic
- Constant
- Quadratic
Hints
- Judge by behaviour for LARGE n, not by which looks more complicated to write.
- Linearithmic sits between linear and quadratic, because the extra factor is a logarithm rather than another n.
Show the answer
- Constant
- Logarithmic
- Linear
- Linearithmic
- Quadratic
- Exponential
Why
The order is constant, logarithmic, linear, linearithmic, quadratic, exponential. Linearithmic is only a logarithm worse than linear, which is why a good sort stays practical on huge inputs while a quadratic sort does not, and why exponential algorithms become impossible at input sizes the others handle easily.
Practise Complexity and Performance Trade-offs
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Complexity and Performance Trade-offs
- Two algorithms are timed on one machine: the O(n) one takes 3 seconds at n = 1000 and the O(n²) one takes 1…
- An O(n log n) sort applied to a nearly-sorted list can be slower than an O(n²) insertion sort on the same…
- A team spends a week optimising a function that accounts for 2% of runtime. What did they get, and what is…
- Big-O notation compares how algorithms scale, so an O(nlog n) algorithm always runs faster than an O(n²) one…