1
Growth is what survives
A machine ten times faster multiplies every cost by 1/10 and changes no growth rate. The classification is about the algorithm.
Lesson · Algorithms and Complexity · Analysis
The Growth of Functions
Comparing algorithms means comparing how their costs grow, not their costs at any one size. Constants and lower-order terms vanish; the gap between polynomial and exponential does not.
1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!
constants and lower-order terms do not affect the class
polynomial vs exponential is a difference of KIND
a faster machine moves the wall; it does not remove it
The hierarchy
Core ideas
What this lesson establishes
Growth rate is the property that survives changes of machine, language and constant factor.
2
Lower-order terms vanish
3n² + 5n + 100 grows like n²: at n = 1000 the quadratic term is 99.8% of the total.
3
Exponential is a different kind
Polynomial costs scale with hardware; exponential ones do not. 2ⁿ at n = 100 exceeds the number of atoms in the observable universe.
The material
Comparing growth
The hierarchy, the numbers behind it, and what a faster machine buys.
n log₂n n log₂n n² 2ⁿ
10 3.3 33 100 1 024
100 6.6 664 10 000 1.3 × 10³⁰
1 000 10.0 9 966 1 000 000 1.1 × 10³⁰¹
1 000 000 20.0 2.0 × 10⁷ 10¹² —
At a million elements, an n log n algorithm does about 20 million operations and an n² algorithm does 10¹² — at a billion operations a second, the difference between a fiftieth of a second and about a quarter of an hour. Both are polynomial; the gap is already decisive.
2ⁿ at n = 100 is 1.27 × 10³⁰. At a billion operations per second that is about 4 × 10¹³ years, roughly three thousand times the age of the universe. No hardware improvement addresses this.
What a faster machine buys
Theorem · Speed-up moves the wall
If a machine becomes k times faster, the largest instance solvable in fixed time grows by a factor of k for a linear algorithm, by √k for a quadratic one, and by only log₂ k ADDED for an exponential one.
Linear: solving n in time T becomes solving kn. Quadratic: n² in time T becomes kn², so the new size is n√k.
Exponential: 2^n in time T becomes k · 2^n = 2^{n + log₂ k}, so the size increases by log₂ k — an additive constant.
□
A thousandfold speed-up lets a linear algorithm handle a thousand times more data, a quadratic one about 32 times more, and an exponential one ten more items. That is the practical meaning of the polynomial/exponential distinction, and it is why “P, NP and NP-Completeness” draws the line where it does.
Lower-order terms
f(n) = 3n² + 5n + 100
n = 10 300 + 50 + 100 = 450 quadratic term is 67%
n = 100 30 000 + 500 + 100 = 30 600 quadratic term is 98%
n = 1000 3 000 000 + 5 000 + 100 quadratic term is 99.8%
So 3n² + 5n + 100 is Θ(n²), and the constant 3 and the additions are discarded — not because they do not exist, but because they do not affect the comparison with an algorithm of a different growth rate.
Constants do matter in practice, and the analysis knows it. An n log n algorithm with a huge constant can lose to an n² one on every input anyone will run, which is why real sort implementations switch to insertion sort for small subarrays. Asymptotic analysis is a tool with known limits, not a complete answer.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Comparing two algorithms
Growth first; constants only when the growth matches.
1
Identify the dominant term
The fastest-growing one. Everything else is discarded for the classification.
2
Compare the classes
Consult the hierarchy. A different class settles the comparison for all large n.
3
If the classes match, look at constants
Two Θ(n log n) algorithms are separated by their constants, and that requires measurement rather than analysis.
4
Check the sizes you actually face
Asymptotics describe large n. If your inputs are always small, the crossover point matters more than the class.
Growth
Score 0 / 0Choose the answer you can justify.
When the worse class wins
Algorithm A costs 100n log₂ n; algorithm B costs n².
A beats B when 100 n log₂ n < n² i.e. 100 log₂ n < n
n = 100 100·6.6 = 664 > 100 B wins
n = 500 100·9.0 = 897 > 500 B wins
n = 1000 100·9.97 = 997 ≈ 1000 the crossover
n = 2000 100·11 = 1100 < 2000 A wins
n = 10⁶ 100·20 = 2000 < 10⁶ A wins by 500×
The asymptotically better algorithm loses on every input below 996,
where 100 log₂ n first drops under n.
Both facts are true and neither is the whole story. A is asymptotically better and B is better on small inputs, and which matters depends on the data. Real sort implementations resolve exactly this by using insertion sort below a threshold of a few dozen elements.
Common mistakes
1
Comparing at one input sizeGrowth is about the trend. An algorithm faster at n = 100 may be hopeless at n = 10⁶.
2
Ignoring constants entirelyThey decide between algorithms of the same class, and they decide the crossover point between different classes.
3
Believing hardware fixes exponential costA thousandfold speed-up buys about ten more items. The wall moves and does not disappear.
Check your understanding
✓
Finish when you can find a crossover point.
Determine where 50n log₂ n overtakes n² and say which algorithm you would use for n = 200 and for n = 10⁶. Both answers are defensible and they are different. To check against: 50 log₂ n first drops under n at n = 439.
Note: The distinction between polynomial and exponential is the one that organises complexity theory. “P, NP and NP-Completeness” makes it the definition of tractability, and every argument there depends on the arithmetic in this lesson's tables.