Linear, polynomial and exponential growth compared
A quantity that adds the same amount each step, one that grows like a square or a cube, and one that multiplies by the same factor each step. Wait long enough, and which one is biggest?
Where you are 6 in Exponential growth and decay
Why this exists
Linear versus exponential growth raced a line against an exponential and found that an increasing exponential always gets past an increasing line in the end. A line is the slowest kind of growth there is, though. A quadratic such as x^2 also grows faster and faster: its steps get longer every time, just as an exponential’s do. A cube grows faster still, and x^{10} faster again. Is there a polynomial that keeps up with 2^x, or even with 1.01^x?
The question matters whenever a model is chosen. Three different rules can fit the same few early measurements and then disagree wildly later on. Knowing which kind of growth wins in the long run, and why, says how far each model can be trusted. This star sets linear, polynomial and exponential growth side by side and proves the answer: an increasing exponential outgrows every polynomial, whatever its degree and however large its coefficients.
Definition
The three kinds of growth compared here are:
- linear growth, f(x) = mx + c with slope m > 0;
- polynomial growth, a polynomial p(x) of degree k \geq 1 with a positive leading coefficient, so p(x) grows without bound as x grows (Degree, end behavior and the shape of a polynomial graph); linear growth is the case k = 1;
- exponential growth, g(x) = a \cdot b^x with a > 0 and b > 1.
A quantity grows without bound when it eventually passes every number you name: for every number M, the quantity is bigger than M for every large enough x.
One function eventually exceeds another when there is a point after which it is always the bigger one: f(x) > h(x) for every x beyond some number N. What happens before N does not matter, and that is the whole point: the head start can be enormous.
For outputs at inputs 0, 1, 2, 3, \dots, the first differences are the steps y(x + 1) - y(x), and the second differences are the differences of those steps. The step factor is \dfrac{y(x + 1)}{y(x)}, the number one step multiplies by.
Intuition
Look at how each family takes its steps.
A line’s steps are all the same length, m.
A quadratic’s steps get longer, but only by a fixed amount each time. For x^2 the steps are 1, 3, 5, 7, 9, \dots: each one is 2 longer than the last. The steps themselves grow linearly. A cubic’s steps grow like a quadratic, and so on up the degrees.
An exponential’s steps grow by a factor. For 2^x the steps are 1, 2, 4, 8, 16, \dots, an exponential again with the same factor 2. However the polynomial’s steps grow, the exponential’s grow in the way that wins.
The step factor tells the same story in one number. For 2^x it is 2 at every step. For x^3 it is \left(\tfrac{x + 1}{x}\right)^3, which is 8 at x = 1, about 1.33 at x = 10 and about 1.03 at x = 100: it sinks toward 1, because adding 1 to a large number hardly changes it in relative terms. Once the cube’s step factor has fallen below 2, every step makes the exponential grow by a bigger factor than the cube, and the cube’s lead, however large, is eaten away.
Results
Step patterns. At equally spaced inputs, a linear function has equal first differences, a quadratic has equal second differences, and an exponential a \cdot b^x has equal step factors b. The first differences of a \cdot b^x are a(b - 1) \cdot b^x: an exponential with the same factor b, so its differences of every order grow by the factor b and never level off.
An exponential outgrows every power. If b > 1 and k is any positive whole number, then
An exponential eventually exceeds every polynomial. If a > 0 and b > 1, and p(x) is any polynomial, then a \cdot b^x > p(x) for every large enough x. In particular it eventually exceeds every line, every quadratic and every cubic.
The ladder. A higher power eventually exceeds a lower one: for j > k, \dfrac{x^j}{x^k} = x^{j - k} grows without bound. So in the long run linear growth loses to quadratic, quadratic to cubic, and every polynomial to every increasing exponential.
Decay beats any power. If 0 < c < 1 and k is a positive whole number, then x^k \cdot c^x comes ever closer to 0 as x grows.
Why it is true
A fixed factor above 1, repeated, is unbounded. For r > 0 and every whole number n \geq 0,
This is true for n = 0, where both sides are 1. If it is true for some n, multiply both sides by the positive number 1 + r:
so it is true for n + 1, and so on for every n. Since 1 + nr grows without bound, so does (1 + r)^n.
The quotient b^n / n^k is unbounded. Take b > 1 and a positive whole number k, and let q(n) = \dfrac{b^n}{n^k} for whole numbers n \geq 1. One step multiplies q by
Expanding \left(1 + \tfrac{1}{n}\right)^k by the binomial theorem gives 1 plus terms \binom{k}{j} \tfrac{1}{n^j}, each at most \binom{k}{j} \tfrac{1}{n}, and the \binom{k}{j} add up to less than 2^k. So \left(1 + \tfrac{1}{n}\right)^k \leq 1 + \tfrac{2^k}{n}, which is at most \displaystyle \sqrt{b} as soon as n \geq N, where N is a whole number at least \displaystyle \dfrac{2^k}{\sqrt{b} - 1}. From N on, each step multiplies q by at least \displaystyle \dfrac{b}{\sqrt{b}} = \sqrt{b}, a fixed factor above 1. So \displaystyle q(N + m) \geq q(N) \cdot (\sqrt{b})^m, and by the first part this grows without bound as m grows.
Between whole numbers. For x \geq 1, let n be the whole number with n \leq x < n + 1. Then b^x \geq b^n, and x^k < (n + 1)^k \leq (2n)^k = 2^k n^k, so \dfrac{b^x}{x^k} > \dfrac{q(n)}{2^k}, which also grows without bound.
Any polynomial. Write p(x) = c_k x^k + \dots + c_1 x + c_0 and let M = |c_k| + \dots + |c_1| + |c_0|. For x \geq 1 every power x^j with j \leq k is at most x^k, so p(x) \leq M x^k. Because \dfrac{b^x}{x^k} grows without bound, it is eventually bigger than \dfrac{M}{a}, and then
The case k = 1 is the full proof promised in Linear versus exponential growth that an increasing exponential gets past every line.
Decay. With b = \tfrac{1}{c} > 1, x^k \cdot c^x = \dfrac{x^k}{b^x}, the reciprocal of a quantity that grows without bound, so it comes ever closer to 0.
Worked examples
Three tables, three families
Name the family of each table, and say which output is biggest at x = 5 and which in the long run.
| x | A | B | C |
|---|---|---|---|
| 0 | 40 | 40 | 40 |
| 1 | 55 | 42 | 60 |
| 2 | 70 | 48 | 90 |
| 3 | 85 | 58 | 135 |
| 4 | 100 | 72 | 202.5 |
| 5 | 115 | 90 | 303.75 |
The inputs go up by 1, so the steps can be compared directly.
A: the first differences are 15, 15, 15, 15, 15. Equal first differences, so A is linear: 40 + 15x.
B: the first differences are 2, 6, 10, 14, 18, not equal, but each is 4 more than the one before. Equal second differences, so B is quadratic. The pattern 40, 42, 48, 58 is 40 plus twice a square: 40 + 2x^2.
C: the first differences are 20, 30, 45, 67.5, 101.25, and the second differences are not equal either. The step factors are \tfrac{60}{40} = 1.5, \tfrac{90}{60} = 1.5, and so on: equal factors, so C is exponential, 40(1.5)^x. Its differences have the same factor: \tfrac{30}{20} = \tfrac{45}{30} = 1.5.
At x = 5, C is biggest, then A, then B. The quadratic is still behind the line, but its steps grow by 4 each time while the line’s stay 15; 40 + 2x^2 > 40 + 15x exactly when 2x > 15, so B passes A at x = 8, where 168 > 160. In the long run C stays ahead of both: it already leads, and its steps grow by a factor.
Catching a line with a long lead
Compare f(x) = 700 + 60x with g(x) = 4(1.3)^x at whole numbers x \geq 0, and find where g first takes the lead.
SolutionThe line starts 696 ahead. Five steps of g multiply it by 1.3^5 = 3.71293, so jump five at a time first, then go one step at a time near the crossing. Values of g are rounded to two decimal places.
| x | f(x) | g(x) |
|---|---|---|
| 0 | 700 | 4 |
| 5 | 1{,}000 | 14.85 |
| 10 | 1{,}300 | 55.14 |
| 15 | 1{,}600 | 204.74 |
| 20 | 1{,}900 | 760.20 |
| 21 | 1{,}960 | 988.26 |
| 22 | 2{,}020 | 1{,}284.74 |
| 23 | 2{,}080 | 1{,}670.16 |
| 24 | 2{,}140 | 2{,}171.20 |
At x = 20 the line is still more than twice as big. Four steps later g leads: g first takes the lead at x = 24. It stays ahead, because each step of g adds 30\% of its value, already more than 0.3 \times 2171 \approx 651, against the line’s fixed 60.
A cube against doubling
Compare x^3 and 2^x. Where is each one bigger?
SolutionWhole numbers first.
| x | x^3 | 2^x |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 2 |
| 2 | 8 | 4 |
| 3 | 27 | 8 |
| 5 | 125 | 32 |
| 8 | 512 | 256 |
| 9 | 729 | 512 |
| 10 | 1{,}000 | 1{,}024 |
| 11 | 1{,}331 | 2{,}048 |
2^x is bigger at x = 0 and x = 1, the cube from x = 2 to x = 9, and 2^x again from x = 10 on. So the graphs cross twice: once between 1 and 2, and once between 9 and 10 (Figure 1). For negative x, x^3 is negative while 2^x is positive, so 2^x is bigger there too.
Why does 2^x stay ahead after x = 10? Its step factor is 2. The cube’s is \left(1 + \tfrac{1}{x}\right)^3, which at x = 10 is 1.331 and only shrinks as x grows. From x = 10 on, each step multiplies 2^x by more than it multiplies x^3, so a lead, once taken, only widens.
Three models for the same start
A new video has 1{,}000 views on day 0 and 1{,}200 on day 1. Three models fit both numbers:
What does each predict for day 10 and day 30? From which day does E predict more than Q?
SolutionCheck the fit first: L(1) = 1200, Q(1) = 1000 + 100 + 100 = 1200, E(1) = 1000 \times 1.2 = 1200, and all three give 1{,}000 on day 0.
Day 10: L(10) = 3{,}000, Q(10) = 1000 + 1000 + 10000 = 12{,}000 and E(10) = 1000(1.2)^{10} \approx 6{,}192. The quadratic predicts the most.
Day 30: L(30) = 7{,}000, Q(30) = 1000 + 3000 + 90000 = 94{,}000 and E(30) \approx 237{,}376. Now the exponential is more than twice the quadratic.
E passes L almost at once: E(2) = 1{,}440 against L(2) = 1{,}400. Passing Q takes much longer. Rounded to the nearest view:
| day d | 20 | 21 | 22 |
|---|---|---|---|
| Q(d) | 43{,}000 | 47{,}200 | 51{,}600 |
| E(d) | 38{,}338 | 46{,}005 | 55{,}206 |
E predicts more than Q from day 22. It stays ahead: Q’s step factor on day 22 is \tfrac{Q(23)}{Q(22)} = \tfrac{56200}{51600} \approx 1.09 and only shrinks after that, while E’s is 1.2 every day. Figure 2 shows the three predictions. Two days of data cannot tell these models apart; their predictions a month out differ by a factor of more than 30. Choosing between them takes more data (Judging and comparing models).
A slow exponential against a cube
The exponential 1.05^x grows by only 5\% a step. Show that it still overtakes x^3, and find where.
SolutionAt small x the cube is far ahead: at x = 2 it is 8 against 1.1025. Look at step factors. 1.05^x is multiplied by 1.05 at every step. The cube is multiplied by \left(1 + \tfrac{1}{x}\right)^3:
The cube’s factor is below 1.05 exactly when 1 + \tfrac{1}{x} < 1.05^{1/3} \approx 1.01640, that is when x > 60.99, so from x = 61 on. From there the quotient \dfrac{1.05^x}{x^3} grows at every step. It starts tiny, since 1.05^{61} \approx 19.61 against 61^3 = 226{,}981, so the catching up is slow. A calculator table near the crossing, rounded to whole numbers:
| x | 362 | 363 |
|---|---|---|
| x^3 | 47{,}437{,}928 | 47{,}832{,}147 |
| 1.05^x | 46{,}830{,}227 | 49{,}171{,}738 |
1.05^x is bigger from x = 363 on (it is also bigger at x = 0 and x = 1, where the cube is 0 and 1). Because the quotient keeps growing from x = 61, the lead never changes hands again. A slow exponential still wins; it just takes longer.
Proving a lead lasts forever
Show that 2^n > n^4 for every whole number n \geq 17.
SolutionA table can only check finitely many values, so argue step by step.
Start: 2^{17} = 131{,}072 and 17^4 = 83{,}521, so the claim holds at n = 17.
Step: suppose 2^n > n^4 for some n \geq 17. One step doubles the left side, 2^{n+1} = 2 \cdot 2^n > 2n^4. The right side is multiplied by \left(1 + \tfrac{1}{n}\right)^4, and with n \geq 17 this is at most \left(\tfrac{18}{17}\right)^4 \approx 1.257, which is less than 2. So
The claim at n gives the claim at n + 1, then at n + 2, and so on: it holds for every whole n \geq 17. This is proof by induction.
The starting point matters. At n = 16 the two are equal, 2^{16} = 16^4 = 65{,}536, and at n = 15 the power is ahead, 32{,}768 < 50{,}625.
Boundaries
“Eventually” can be very late. The results say who wins, not when. 1.05^x needs until x = 363 to pass x^3, and a smaller base or a bigger polynomial pushes the crossing further out. Over a short range a polynomial can be far ahead, and in many real situations that short range is all that matters.
The exponential must increase. The results need a > 0 and b > 1. With 0 < b < 1 the exponential shrinks toward 0 and every polynomial with a positive leading coefficient ends up above it. With a < 0 the exponential heads down without bound.
Large x only. The comparison is about x growing. For negative x an increasing exponential comes ever closer to 0, while a polynomial does whatever its degree says (Degree, end behavior and the shape of a polynomial graph).
Tables show only their rows. Equal second differences or equal factors over a few rows say those rows fit a quadratic or an exponential; they do not say what happens beyond them. Different families can fit the same short table exactly, as in Example 4.
Models stop being true. No real quantity grows exponentially for ever: space, food or money run out, and growth levels off (Logistic growth: when growth levels off). The results are about the functions, and a model built from one is trusted only over the range where it fits the data.
Where this goes next
Judging and comparing models compares a model’s predictions with new data and spots where linear, quadratic and exponential models begin to drift apart, which this star shows they must. Logistic growth: when growth levels off covers growth that starts out nearly exponential and then levels off. The step factors and the quotient \dfrac{b^x}{x^k} return in calculus, where growth rates are compared with limits; the statement that \dfrac{b^x}{x^k} grows without bound is the fact behind many of those comparisons.
Exercises
Which family?
For each table, name the family (linear, quadratic, exponential or none of these) and give the equal differences, second differences or factor.
- x: 0, 1, 2, 3, 4, 5; y: 3, 5, 9, 15, 23, 33.
- x: 0, 1, 2, 3, 4; y: 4, 10, 25, 62.5, 156.25.
- x: 0, 1, 2, 3, 4; y: 11, 19, 27, 35, 43.
- x: 0, 1, 2, 3, 4; y: 1, 2, 5, 14, 41.
- x: 0, 1, 2, 3, 4; y: 50, 45, 32, 11, -18.
Steps of each family
- For g(x) = 5(2)^x, find g(x + 1) - g(x). What do you notice?
- For q(x) = 3x^2 + 11x, find q(x + 1) - q(x) and the second difference.
- For h(x) = 7(1.4)^x, find h(x + 1) - h(x), and the factor between one difference and the next.
Who is ahead, and where
- For whole numbers x from 0 to 9, say where x^4 is bigger and where 3^x is bigger. Which is bigger for every whole x after that?
- Find the first whole x \geq 2 where 1.4^x > x^2.
- Find the first whole x \geq 1 where 2^x > 80x^2.
- Find the first whole x where 3(1.25)^x > 200 + 45x.
- A library has 500 members in year 0 and 550 in year 1. Three models fit: L(t) = 500 + 50t, Q(t) = 500 + 25t + 25t^2 and E(t) = 500(1.1)^t. Find each prediction for year 10 and year 40, and the first whole t \geq 2 where E(t) > Q(t).
Step factors
- Find the step factor \dfrac{(x + 1)^2}{x^2} of x^2 at x = 1, 10 and 100. From which whole x is it below 1.1, the step factor of 1.1^x?
- Let q(n) = \dfrac{2^n}{n^3}. Find q(3), q(4) and q(5), and show that q(n + 1) > q(n) for every whole n \geq 4 but not for n = 3.
Reasoning
- Use (1 + r)^n \geq 1 + nr to show that 1.01^{100000} > 1000, without a calculator.
- Tadeo says x^{10} grows faster than 1.01^x, because at x = 100 the power is 10^{20} while 1.01^{100} is less than 3. Is he right in the long run? Find the first whole x from which the step factor of x^{10} is below 1.01, and explain what that means.
- Explain why x^2(0.5)^x comes ever closer to 0 as x grows, even though x^2 grows without bound.
- Is 1.001^x eventually bigger than 1{,}000{,}000x^2? Explain using the results, without finding where.
Answers
- Quadratic. First differences 2, 4, 6, 8, 10; second differences all 2.
- Exponential with factor 2.5: \tfrac{10}{4} = \tfrac{25}{10} = \tfrac{62.5}{25} = \tfrac{156.25}{62.5} = 2.5.
- Linear. First differences all 8.
- None of these. First differences 1, 3, 9, 27 and second differences 2, 6, 18 are not equal, and the ratios 2, 2.5, 2.8, about 2.93 are not either. The first differences have factor 3: the table is \tfrac{3^x + 1}{2}, an exponential plus a constant.
- Quadratic. First differences -5, -13, -21, -29; second differences all -8.
- g(x + 1) - g(x) = 5 \cdot 2^{x+1} - 5 \cdot 2^x = 5(2)^x. The differences of g are g itself, since b - 1 = 1.
- q(x + 1) - q(x) = 3(2x + 1) + 11 = 6x + 14, a linear expression; its steps are all 6, so the second difference is 6.
- h(x + 1) - h(x) = 7(1.4)^x(1.4 - 1) = 2.8(1.4)^x. Each difference is 1.4 times the one before.
- 3^x is bigger at x = 0 and 1 (1 > 0, 3 > 1). x^4 is bigger from x = 2 to x = 7; at 7 it is 2{,}401 against 2{,}187. 3^x is bigger at 8 (6{,}561 > 4{,}096) and 9, and for every whole x after that.
- x = 17. At 16: 1.4^{16} \approx 217.80, less than 256. At 17: 1.4^{17} \approx 304.91, more than 289.
- x = 14. At 13: 2^{13} = 8192, less than 80 \times 169 = 13520. At 14: 2^{14} = 16384, more than 80 \times 196 = 15680.
- x = 28. At 27: 3(1.25)^{27} \approx 1240.77, less than 1415. At 28: about 1550.96, more than 1460.
- Year 10: L = 1000, Q = 3250, E \approx 1296.87. Year 40: L = 2500, Q = 41500, E \approx 22629.63. At t = 51: Q = 66800 against E \approx 64564.97; at t = 52: Q = 69400 against E \approx 71021.47. So t = 52.
- 4, 1.21 and 1.0201. At x = 20 it is 1.1025 and at x = 21 it is \left(\tfrac{22}{21}\right)^2 \approx 1.0975, so from x = 21 on.
- q(3) = \tfrac{8}{27} \approx 0.296, q(4) = \tfrac{1}{4}, q(5) = \tfrac{32}{125} = 0.256. The step factor is \displaystyle \dfrac{q(n + 1)}{q(n)} = \dfrac{2}{\left(1 + \frac{1}{n}\right)^3}, which is above 1 exactly when \left(1 + \tfrac{1}{n}\right)^3 < 2. At n = 3 it is \tfrac{64}{27} \approx 2.37, too big; at n = 4 it is \tfrac{125}{64} \approx 1.95, and it only shrinks as n grows. So q grows at every step from n = 4 on.
- With r = 0.01 and n = 100000: 1.01^{100000} \geq 1 + 100000 \times 0.01 = 1001, which is more than 1000.
- Not in the long run. 1.01^{100} \approx 2.70 and the power is far ahead there, but the step factor \left(1 + \tfrac{1}{x}\right)^{10} of x^{10} is below 1.01 from x = 1005 on (at 1004 it is just above). From then on every step multiplies 1.01^x by more than it multiplies x^{10}, so \dfrac{1.01^x}{x^{10}} grows at every step, and by the results it grows without bound: 1.01^x eventually passes x^{10}, though only at a very large x.
- x^2(0.5)^x = \dfrac{x^2}{2^x}, which is 1 divided by \dfrac{2^x}{x^2}. That quotient grows without bound, because 2 > 1, so its reciprocal comes ever closer to 0. The halving at each step beats the growth of x^2, whose step factor sinks toward 1.
- Yes. 1{,}000{,}000x^2 is a polynomial and 1.001^x is a \cdot b^x with a = 1 > 0 and b = 1.001 > 1, so by the results 1.001^x > 1{,}000{,}000x^2 for every large enough x. Equivalently, \dfrac{1.001^x}{x^2} grows without bound, so it eventually passes 1{,}000{,}000. The crossing is very far out, but it exists.