Polynomial, Exponential and Logarithmic Growth

Three families in one table

Three kinds of function grow without limit: logarithms such as ${\log }_{2}n$log₂n, powers such as $n^2$n², and exponentials such as $2^n$2ⁿ. For small n it is hard to tell them apart, and the order can even change.

At n = 4, $n^2=16$n² = 16 and $2^n=16$2ⁿ = 16, while ${\log }_{2}n=2$log₂n = 2. At n = 8 the three are 3, 64 and 256. At n = 16 they are 4, 256 and 65536. Doubling n adds 1 to ${\log }_{2}n$log₂n, multiplies $n^2$n² by 4, and squares $2^n$2ⁿ.

Before n = 4 the two are not in this order everywhere. At n = 3, $n^2=9$n² = 9 is larger than $2^3=8$2³ = 8, and they are equal at n = 2, where both are 4. From n = 5 on, $2^n$2ⁿ is ahead and stays ahead: 32 against 25, then 64 against 36.

The gold curve is $y=2^x$y = 2ˣ and the plain curve is $y=x^2$y = x². They meet at x = 2 and at x = 4. Between them $x^2$x² is higher, 9 against 8 at x = 3; beyond x = 4, $2^x$2ˣ pulls away, 64 against 36 at x = 6.

One order, in the long run

The three families rank in one order once n is large enough: every logarithm is below every power $n^k$nᵏ with k > 0, and every power is below every exponential $a^n$aⁿ with a > 1. No choice of constants changes that order. A constant in front, such as $1000n^2$1000n², only moves the point where the order takes over.

The words "large enough" carry the meaning. Compare $\sqrt{n}$√n, the power with $k=\frac{1}{2}$k = 1/2, with ${\log }_{2}n$log₂n. They are equal at n = 4, where both are 2, and at n = 16, where both are 4. Between those two the logarithm is ahead: at n = 8, ${\log }_{2}n=3$log₂n = 3 and $\sqrt{8}$√8 is about 2.83. From n = 17 on, $\sqrt{n}$√n is ahead for good.

A small power can take a very long time. The tenth root of x is below ln x from about x = 3.06 until x is about $3.4\times 10^{15}$3.4 × 10¹⁵, and above it from there on.

A small base also only delays the crossing. $1.1^n$1.1ⁿ grows by just a tenth each step, yet it passes $n^2$n² for good at n = 96: $1.1^{96}$1.1⁹⁶ is about 9412, and $96^2=9216$96² = 9216.

The gold curve is $y=\sqrt{x}$y = √x and the plain curve is $y={\log }_{2}x$y = log₂x. They cross at x = 4 and at x = 16; between the two crossings the logarithm is higher, and after x = 16 the square root stays above it.

A large power only delays the crossing

Raising the power pushes the crossing point further out. $2^n$2ⁿ passes $n^2$n² for good at n = 5, $n^3$n³ at n = 10, where $2^{10}=1024$2¹⁰ = 1024 and $10^3=1000$10³ = 1000, and $n^{10}$n¹⁰ at n = 59.

Even $n^{100}$n¹⁰⁰ is overtaken. At n = 996, $n^{100}$n¹⁰⁰ is still the larger, by a hair; from n = 997 on, $2^n$2ⁿ is ahead and never falls behind again. The crossing is late, but it comes.

The first n from which $2^n$2ⁿ is larger than each power for every n after it. The power goes up fifty-fold from $n^2$n² to $n^{100}$n¹⁰⁰, and the crossing moves from 5 to 997.

Why the exponential must win

Compare what one step does to each. Going from n to n + 1 multiplies $2^n$2ⁿ by 2, always. It multiplies $n^k$nᵏ by $\frac{{\left(n+1\right)}^k}{n^k}={\left(1+\frac{1}{n}\right)}^k$(n + 1)ᵏ/nᵏ = (1 + 1/n)ᵏ, and that factor falls toward 1 as n grows, because $\frac{1}{n}$1/n falls toward 0.

For k = 100, the factor ${\left(1+\frac{1}{n}\right)}^{100}$(1 + 1/n)¹⁰⁰ is below 1.5 from n = 247 on. From there, each step multiplies the ratio $\frac{n^{100}}{2^n}$n¹⁰⁰/2ⁿ by less than 1.5 ÷ 2 = 0.75. A number cut by at least a quarter at every step falls toward 0, however large it starts, so the ratio drops below 1, and then $2^n$2ⁿ is the larger.

The same argument works for any power k and any base a > 1. In the end ${\left(1+\frac{1}{n}\right)}^k$(1 + 1/n)ᵏ falls below any number larger than 1, so it falls below a number c between 1 and a, and from then on each step multiplies the ratio $\frac{n^k}{a^n}$nᵏ/aⁿ by less than $\frac{c}{a}$c/a, which is less than 1.

Written as limits

The order can be written with limits: $\frac{n^k}{a^n}\to 0$nᵏ/aⁿ → 0 as $n\to \infty$n → ∞ for every k and every a > 1, and $\frac{{\log }_{2}n}{n}\to 0$log₂n/n → 0 as well. A ratio that tends to 0 says the bottom outgrows the top.

The fall need not start at once. The ratio $\frac{n^3}{2^n}$n³/2ⁿ is 0.5 at n = 1, rises to 4 at n = 4, and only then falls: about 0.98 at n = 10 and about 0.0076 at n = 20.

The logarithm limit is the same fact in disguise. Put n = 2ᵐ. Then ${\log }_{2}n=m$log₂n = m, so $\frac{{\log }_{2}n}{n}=\frac{m}{2^m}$log₂n/n = m/2ᵐ, which is a power over an exponential with k = 1, and it tends to 0.

The ratio $\frac{n^3}{2^n}$n³/2ⁿ. At the whole numbers its largest value is 4, at n = 4; after that it sinks toward 0, and by n = 20 it is below 0.01.

The usual mistakes

Reading the order as true for every n. $2^n$2ⁿ is not larger than $n^2$n² at n = 3, and ${\log }_{2}n$log₂n is larger than $\sqrt{n}$√n at n = 8. The order says what happens from some point on.

Trusting a large power. $n^{100}$n¹⁰⁰ is ahead of $2^n$2ⁿ for a long stretch, from n = 2 up to n = 996, and is still overtaken.

Treating a faster computer as a fix for exponential work. A machine 64 times as fast lets a job of $2^n$2ⁿ steps grow by only 6, because $64=2^6$64 = 2⁶, while a job of $n^2$n² steps grows 8 times, because $64=8^2$64 = 8².

Sorting, searching and forecasting

In the first application, $32n{\log }_{2}n$32n log₂n and $n^2$n² steps are compared at powers of 2, where the logarithm is a whole number, and they are equal at n = 256. The second sets computers that double in speed every 2 years against a model whose running time grows as a fourth power.