Functions and Their Growth Rates

Functions and Their Growth Rates

Every algorithm's cost is a function: feed it the input size n and it returns the number of basic operations. This page is the field guide to those functions — the handful of growth classes you meet again and again, exactly how fast each one explodes in raw numbers, and the dominance rules that stack them in an order that never reverses. Knowing the definition of Big-O tells you how to write a bound; knowing the zoo tells you what a bound means the instant you see it.

The formal ∃c,n0 definition lives on Big-O Notation, and the method for deriving a bound from code is on Understanding Time Complexity. Here we take the classes as given and study their behaviour.

The zoo, in raw operation counts

Abstract rankings do not land until you see the numbers. Here is the actual operation count for each class at four input sizes:

Read the last two rows. At a million items O(n2) is a trillion operations (minutes to hours); O(2n) passes the number of atoms in the universe by n = 300. Meanwhile O(log n) crawls from 3 to 20 across the entire table — six orders of magnitude of input for a 6× rise in work. That flatness is why logarithmic operations feel free.

Dominance: the order that never reverses

For large n the classes stack in a fixed hierarchy, and two rules generate it:

• Any polynomial beats any polylogarithm. na eventually exceeds (log n)b for every pair of positive constants a, b — even n0.1 outgrows (log n)100 in the limit. This is why O(n) is a real step up from O(log n), not a near-tie.
• Any exponential beats any polynomial. bn (b > 1) eventually exceeds nk for every constant k.

The crossover that makes rule two concrete. "My algorithm is only polynomial — degree 10, sure, but polynomial" sounds safer than exponential. Is it? Compare 2n against the enormous polynomial n10. Set them equal: 2n = n10 ⇒ n·ln2 = 10·ln n ⇒ n/ln n = 10/ln2 ≈ 14.4. Solving gives n ≈ 59: below 59, the degree-10 polynomial is actually the larger count; at n = 59 the exponential overtakes it and never looks back (259 ≈ 5.8×1017 vs 5910 ≈ 5.1×1017). So even a grotesque polynomial is dominated by a modest exponential past a small threshold — the hierarchy is not a suggestion.

Reading a growth curve like an engineer

On an ordinary linear plot (above, and the interactive) the curves tangle near the origin — small n hides everything. The professional trick is the log-log plot: plot log T(n) against log n. Then any power law T = nk becomes a straight line whose slope is exactly k (because log(nk) = k·log n). Linear is a line of slope 1, quadratic slope 2 — you can read the exponent straight off the chart, and it is exactly how you turn benchmark timings into an empirical growth class. Exponentials refuse to straighten: they still curve upward even on log-log, which is the instant visual tell that you are not looking at a polynomial.

Pitfalls specific to comparing growth rates

• Treating log n and n log n as neighbours. They differ by a factor of n — at a million, that is 20 vs 20 million. The shared "log" hides an enormous gap.
• Thinking n1.01 ≈ n. Their ratio is n0.01 → ∞; the class is strictly larger. Small exponent gaps still compound at scale.
• Log base vs exponent base. The base of a logarithm is only a constant factor (log2n and log10n differ by 3.32×), so all logs are one class O(log n). The base of an exponent is not: 3n/2n = 1.5n → ∞, so 2n and 3n are genuinely different classes. Never simplify an exponent's base the way you drop a log's.

Key takeaways

• The growth zoo runs O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!); the raw-count table shows why the top of that list becomes physically impossible fast.
• Dominance rules: every polynomial eventually beats every polylog; every exponential eventually beats every polynomial — e.g. 2n overtakes even n10 by n ≈ 59.
• Read curves on a log-log plot: a power law is a straight line of slope = its exponent; exponentials still curve.
• Drop a logarithm's base (constant factor); never drop an exponent's base (different class).