Comparing growth rates at infinity
Two functions both grow without bound. How do you say, exactly, that one of them leaves the other behind, and which of the familiar families wins?
Where you are 11 in Limits
Why this exists
Pao, Txawj and Nou are comparing computer programs. For each one they measure the running time as a function of the input size x: how long the program takes on a list of x items, say. A program whose time is x^2 and one whose time is 2^x both take longer and longer as x grows, so “both go to infinity” says nothing useful. What they want to know is which one becomes hopeless first, and whether a head start on small inputs ever lasts.
Plugging in a few values does not settle it. A function can trail for millions of inputs and then pull ahead for good. The question needs a limit: compare the two functions by their quotient, far out, where the head start no longer matters. That comparison sorts the functions met so far into a ladder, logarithms at the bottom, powers in the middle and exponentials at the top, and the ladder then hands over limits such as \lim_{x \to \infty} x^2 e^{-x} with no computation at all.
Definition
Let f and g be positive for all large x. Compare them by the quotient \dfrac{f(x)}{g(x)} as x \to \infty.
- f grows faster than g (and g grows slower than f) when
- f and g grow at the same rate when \lim_{x \to \infty} \dfrac{f(x)}{g(x)} = L for a number L with 0 < L < \infty.
The two forms in the first line say the same thing: a positive quotient grows without bound exactly when its reciprocal shrinks to 0. As always, = \infty is a way of saying how a limit fails to exist as a number, not a number itself.
The definition ignores constant factors on purpose. If f(x) = 1000x^2 and g(x) = x^2, the quotient is always 1000, so they grow at the same rate: a program a thousand times slower on every input is slower, but it is not in a different class. The definition also ignores any finite stretch of inputs, since a limit at infinity looks only at what happens past every point.
Intuition
The quotient \dfrac{f(x)}{g(x)} answers the question “how many copies of g fit inside f?” If f grows faster, that count eventually exceeds a million, then a billion, then anything. It may first rise and fall many times, and it may be tiny for a long while. Only the eventual behavior counts.
Figure 1 shows how badly a few values can mislead. The quotient \dfrac{x^4}{1.03^x} climbs to about six million near x = 135. Someone who stopped there would say x^4 is far ahead. But the exponential multiplies by 1.03 at every unit step forever, while the power’s growth slows, and by x = 1000 the quotient is below 1. From then on it heads to 0: the exponential grows faster.
The same picture is true up and down the ladder. A logarithm such as \ln x grows, but so slowly that any positive power of x, even x^{0.01}, eventually leaves it behind. Any power, even x^{100}, is eventually left behind by any exponential a^x with a > 1, even 1.0001^x. A comparison of exponentials against straight lines with step factors and tables is in Linear, polynomial and exponential growth compared; here the comparison is made by limits and covers every power and every logarithm at once.
Results
The ladder. For all constants p > 0, q > 0 and a > 1:
In words: every power of \ln x grows slower than every positive power of x, and every power of x grows slower than every exponential with base above 1. Within the powers, x^p grows slower than x^r when p < r, because \dfrac{x^p}{x^r} = \dfrac{1}{x^{r - p}} \to 0. Within the exponentials, a^x grows slower than b^x when 1 < a < b, because \dfrac{a^x}{b^x} = \left(\dfrac{a}{b}\right)^x \to 0.
Logarithm bases do not matter. For b > 1, \log_b x = \dfrac{\ln x}{\ln b}, a constant multiple of \ln x, so all logarithms grow at the same rate and the ladder holds for each of them.
Ranking rules. Let all functions be positive for large x.
- Positive constant factors do not change a ranking.
- If f grows faster than g and g faster than h, then f grows faster than h, since \dfrac{h}{f} = \dfrac{h}{g} \cdot \dfrac{g}{f} \to 0 \cdot 0 = 0.
- If g grows slower than f, then f + g grows at the same rate as f, since \dfrac{f + g}{f} = 1 + \dfrac{g}{f} \to 1. A sum takes the rank of its fastest term.
Why it is true
Both ladder limits come from one fact.
Lemma. \displaystyle \displaystyle \lim_{t \to \infty} \frac{t}{e^t} = 0.
Proof. Take t \ge 1 and let n be the integer with n \le t < n + 1, so n \ge 1. Since e > 2 and 2^x is increasing, e^t \ge 2^t \ge 2^n. By the binomial theorem,
So, using t < n + 1 \le 2n,
As t \to \infty the integer n grows without bound, so \dfrac{4}{n} \to 0, and the quotient, trapped between 0 and \dfrac{4}{n}, goes to 0. \square
Powers against exponentials. Let p > 0 and a > 1, so \ln a > 0. Write a^x = e^{x \ln a} and pull out the p-th power:
Put s = \dfrac{x \ln a}{p}. Then x = \dfrac{p}{\ln a}\, s, and s \to \infty as x \to \infty, so the quantity inside the brackets is \dfrac{p}{\ln a} \cdot \dfrac{s}{e^s}, which goes to 0 by the lemma. A positive quantity u going to 0 makes u^p go to 0 too (once u < \varepsilon^{1/p}, u^p < \varepsilon). So \dfrac{x^p}{a^x} \to 0.
Logarithms against powers. Substitute x = e^t, so \ln x = t and t \to \infty exactly when x \to \infty:
That is a power of t over an exponential with base e^p > 1, which goes to 0 by the previous step. So the bottom rung of the ladder is the top rung in disguise: the substitution x = e^t turns logarithms into powers and powers into exponentials. L’Hopital’s rule, later in the course, gives a second proof.
Worked examples
A quadratic running time against a cubic one
Pao’s program takes f(x) = 2x^2 + 30x milliseconds on x items, and Txawj’s takes g(x) = \dfrac{x^3}{50}. Which grows faster? How does f compare with h(x) = x^2?
SolutionDivide by the largest power in the denominator. For x > 0,
The bottom goes to 2 and the top grows without bound, so \lim_{x \to \infty} \dfrac{g(x)}{f(x)} = \infty: Txawj’s program grows faster. It is faster on small inputs, though. At x = 100, f(100) = 23{,}000 and g(100) = 20{,}000. Setting \dfrac{x^3}{50} = 2x^2 + 30x and dividing by \dfrac{x}{50} gives x^2 - 100x - 1500 = 0, whose positive root is \displaystyle x = 50 + 20\sqrt{10} \approx 113.2. Past that, Txawj’s program is the slower one for good.
For the second question, \dfrac{f(x)}{x^2} = 2 + \dfrac{30}{x} \to 2, a number between 0 and \infty. So f grows at the same rate as x^2; the term 30x is a lower rung and drops out, as the sum rule says.
A logarithm that leads for millions of inputs
Txawj has a program whose time is (\ln x)^3 and another whose time is \displaystyle \sqrt{x}. Find \displaystyle \lim_{x \to \infty} \dfrac{(\ln x)^3}{\sqrt{x}}, and explain why a table up to x = 10^6 points the wrong way.
SolutionThe ladder with q = 3 and \displaystyle p = \frac{1}{2} gives
so \displaystyle \sqrt{x} grows faster. Yet at x = 10^6 the quotient is about 2.637: the logarithm is still ahead. At x = 10^{10} it is about 0.1221.
The substitution x = e^t shows why. The quotient becomes \dfrac{t^3}{e^{t/2}}. The two sides are equal where t^3 = e^{t/2}, and solving numerically gives t \approx 1.227 and t \approx 16.999. Between them, from x = e^{1.227} \approx 3.41 to x = e^{16.999} \approx 2.41 \times 10^7, the cube of the logarithm is the larger. Its lead lasts for about twenty-four million inputs, and then it is gone forever, because the quotient goes to 0.
A quotient that climbs to millions before it falls
Nou compares a program taking x^4 steps with one taking 1.03^x steps. Find \lim_{x \to \infty} \dfrac{x^4}{1.03^x} and describe the quotient for moderate x.
SolutionThe base 1.03 is above 1, so the ladder with p = 4 and a = 1.03 gives \lim_{x \to \infty} \dfrac{x^4}{1.03^x} = 0. The exponential grows faster.
For moderate inputs the power is far ahead. A calculator gives:
| x | x^4 / 1.03^x |
|---|---|
| 100 | 5{,}203{,}284 |
| 500 | 23{,}838 |
| 1000 | 0.1455 |
| 1500 | 2.81 \times 10^{-7} |
The quotient peaks at about 6.14 million near x = 135 (Figure 1) and equals 1 near x \approx 924.1, where 4 \ln x = x \ln 1.03. Beyond that the exponential program is the slower one, and the gap only widens. The limit says who wins; it says nothing about when.
A power times a decaying exponential
Find \lim_{x \to \infty} x^2 e^{-x} and \lim_{x \to \infty} \dfrac{e^x}{x^{100}}.
SolutionThe product x^2 e^{-x} is the indeterminate shape \infty \cdot 0: one factor grows, the other shrinks, and the limit laws alone cannot say which wins. Rewrite it as a quotient: x^2 e^{-x} = \dfrac{x^2}{e^x}, a power over an exponential with base e > 1. By the ladder, \lim_{x \to \infty} x^2 e^{-x} = 0.
Figure 2 shows both phases. Near 0 the power controls the shape and the graph rises; its highest point is \displaystyle \left(2, \frac{4}{e^2}\right) \approx (2, 0.541) (finding that peak needs derivatives, later). After that the exponential takes over and pulls the graph down to the x-axis, which is a horizontal asymptote.
For the second limit, \dfrac{x^{100}}{e^x} \to 0 by the ladder, and its reciprocal is positive, so \lim_{x \to \infty} \dfrac{e^x}{x^{100}} = \infty. The limit does not exist as a number: the quotient grows without bound.
A sum takes the rank of its fastest term
Find \displaystyle \displaystyle \lim_{x \to \infty} \frac{2^x + x^5}{3 \cdot 2^x - \ln x}.
SolutionThe fastest term on top and on the bottom is 2^x. Divide top and bottom by it:
By the ladder, \dfrac{x^5}{2^x} \to 0. For the other piece, \dfrac{\ln x}{2^x} = \dfrac{\ln x}{x} \cdot \dfrac{x}{2^x}, a product of two quotients that each go to 0 by the ladder. The bottom therefore goes to 3, which is not 0, so the quotient law applies:
Ranking seven running times
Nou lists seven running times: 5 \ln x, (\ln x)^2, \displaystyle \sqrt{x}, x \ln x, x^{3/2}, 2^x, e^x. Rank them from slowest growing to fastest.
SolutionCheck each neighboring pair with a quotient.
- \dfrac{(\ln x)^2}{5 \ln x} = \dfrac{\ln x}{5} \to \infty, so (\ln x)^2 is above 5 \ln x. The constant 5 cannot save it.
- \dfrac{(\ln x)^2}{x^{1/2}} \to 0 by the ladder, so \displaystyle \sqrt{x} is above (\ln x)^2.
- \displaystyle \dfrac{x \ln x}{\sqrt{x}} = \sqrt{x}\, \ln x \to \infty, so x \ln x is above \displaystyle \sqrt{x}.
- \dfrac{x \ln x}{x^{3/2}} = \dfrac{\ln x}{x^{1/2}} \to 0, so x^{3/2} is above x \ln x. A logarithmic factor counts for less than any power, even x^{1/2}.
- \dfrac{x^{3/2}}{2^x} \to 0 by the ladder, and \dfrac{2^x}{e^x} = \left(\dfrac{2}{e}\right)^x \to 0 because 0 < \dfrac{2}{e} < 1.
By the transitive rule the whole chain holds. From slowest growing to fastest: 5 \ln x, then (\ln x)^2, then \displaystyle \sqrt{x}, then x \ln x, then x^{3/2}, then 2^x, then e^x.
The ladder near zero
Find \displaystyle \lim_{x \to 0^+} x \ln x, and use it to find \displaystyle \lim_{x \to 0^+} x^x.
SolutionAs x \to 0^+, x \to 0 while \ln x \to -\infty: the shape 0 \cdot \infty again. Substitute x = \dfrac{1}{u}. Then u \to \infty exactly when x \to 0^+, and \ln x = -\ln u, so
by the ladder with q = p = 1. So \lim_{x \to 0^+} x \ln x = 0.
For x > 0, x^x = e^{x \ln x}. The exponent goes to 0, and e^u is continuous at 0 (see Continuity), so \lim_{x \to 0^+} x^x = e^0 = 1. A check: 0.1^{0.1} \approx 0.7943 and 0.001^{0.001} \approx 0.9931.
Boundaries
Only the long run. The ladder says who wins as x \to \infty, never where the lead changes. In Example 2 the slower function leads until about 2.41 \times 10^7. For inputs that never get that large, the “faster growing” function may be the smaller one throughout.
The constants matter. The ladder needs p > 0, q > 0 and a > 1. For 0 < a < 1, a^x \to 0 and is not growing at all; for a = 1 it is constant; for p \le 0, x^p does not grow.
The quotient must have a limit. Some pairs are in neither relation. For f(x) = x(2 + \sin x) and g(x) = x, the quotient 2 + \sin x swings between 1 and 3 forever, so f neither grows faster than g nor at the same rate in the sense defined here.
Differences are not quotients. The difference (x^2 + x) - x^2 = x grows without bound, yet \dfrac{x^2 + x}{x^2} \to 1: same rate. Growth rates are compared by quotients only.
Same rate inside an exponent is not enough. 2x and x grow at the same rate, but \dfrac{e^{2x}}{e^x} = e^x \to \infty. A constant factor in the exponent changes the base, and so the rung.
Where this goes next
The ladder answers limits of the shapes \dfrac{\infty}{\infty} and 0 \cdot \infty whenever the pieces are logarithms, powers and exponentials, and it shows where graphs flatten toward horizontal asymptotes. Once derivatives are in hand, L’Hopital’s rule turns these comparisons into a general method and proves the ladder a second way. The same comparison, by quotient, later decides whether infinite sums add up to a finite number, and it is how running times of programs are classified: a program counts as practical or hopeless by its rung, not by its value at one input.
Exercises
Using the definition
For each pair, decide whether f grows faster than g, slower than g, or at the same rate. Give the limit of \dfrac{f(x)}{g(x)}.
- f(x) = 5x^3 - x, g(x) = x^3 + 4x^2.
- f(x) = x^2 \ln x, g(x) = x^2.
- f(x) = \log_{10} x, g(x) = \ln x.
- f(x) = 4^x, g(x) = 2^x.
- \displaystyle f(x) = \sqrt{x^2 + 1}, g(x) = x.
Limits from the ladder
Find each limit, writing \infty for a quotient that grows without bound.
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{\ln x}{x^{0.1}}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{x^{20}}{e^x}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{e^x}{x^3}
- \displaystyle \lim_{x \to \infty} x^3 e^{-2x}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{(\ln x)^5}{x}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{3e^x + x^4}{e^x + 7x^2}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{x^2 + \ln x}{2x^2 - \sqrt{x}}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{2^x - x^{10}}{2^x + x^{10}}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{x^5 + 3^x}{2^x + 4^x}
- \displaystyle \displaystyle \lim_{x \to \infty} \frac{\ln(x^4)}{(\ln x)^2}
Running times and substitutions
- Rank from slowest growing to fastest: x^{0.5}, (\ln x)^{10}, \dfrac{x}{\ln x}, 1.001^x, x^2.
- Txawj’s program takes x(\ln x)^2 seconds and Pao’s takes x^{1.2} seconds. Which is smaller at x = 10^6? Which is smaller for all large enough x?
- Show that x^{30} > 2^x at x = 100 but 2^x > x^{30} at x = 300. Which grows faster?
- Find \displaystyle \displaystyle \lim_{x \to 0^+} \sqrt{x}\, \ln x.
- Find \displaystyle \lim_{x \to \infty} x^{1/x}.
- Find \displaystyle \lim_{x \to -\infty} x^2 e^{x}.
Reasoning
- Prove: if f and g grow at the same rate and g grows faster than h, then f grows faster than h.
- Explain why \log_2 x and \ln x grow at the same rate while 2^x and e^x do not.
- Prove that \displaystyle e^{\sqrt{x}} grows faster than every power x^p with p > 0.
- Show that x^{\ln x} grows faster than every power x^p but slower than 2^x.
Answers
- Same rate; the limit is 5. Dividing top and bottom by x^3 gives \dfrac{5 - 1/x^2}{1 + 4/x} \to 5.
- f grows faster; \dfrac{x^2 \ln x}{x^2} = \ln x \to \infty.
- Same rate; \dfrac{\log_{10} x}{\ln x} = \dfrac{1}{\ln 10} \approx 0.434 for every x > 1.
- f grows faster; \dfrac{4^x}{2^x} = 2^x \to \infty.
- Same rate; the limit is 1. For x > 0, \displaystyle \dfrac{\sqrt{x^2 + 1}}{x} = \sqrt{1 + 1/x^2} \to 1.
- 0. The ladder with q = 1, p = 0.1.
- 0. The ladder with p = 20, a = e.
- \infty. The reciprocal \dfrac{x^3}{e^x} goes to 0 through positive values.
- 0. x^3 e^{-2x} = \dfrac{x^3}{(e^2)^x} and e^2 > 1.
- 0. The ladder with q = 5, p = 1.
- 3. Divide by e^x: \dfrac{3 + x^4/e^x}{1 + 7x^2/e^x} \to \dfrac{3 + 0}{1 + 0}.
- \dfrac{1}{2}. Divide by x^2: \dfrac{1 + (\ln x)/x^2}{2 - x^{-3/2}} \to \dfrac{1}{2}, since \dfrac{\ln x}{x^2} \to 0.
- 1. Divide by 2^x: \dfrac{1 - x^{10}/2^x}{1 + x^{10}/2^x} \to \dfrac{1 - 0}{1 + 0}.
- 0. Divide by 4^x: \dfrac{x^5/4^x + (3/4)^x}{(1/2)^x + 1} \to \dfrac{0 + 0}{0 + 1}.
- 0. \ln(x^4) = 4 \ln x, so the quotient is \dfrac{4}{\ln x} \to 0.
- (\ln x)^{10}, x^{0.5}, \dfrac{x}{\ln x}, x^2, 1.001^x. Quotients: \dfrac{(\ln x)^{10}}{x^{0.5}} \to 0; \dfrac{x^{0.5}}{x/\ln x} = \dfrac{\ln x}{x^{0.5}} \to 0; \dfrac{x/\ln x}{x^2} = \dfrac{1}{x \ln x} \to 0; \dfrac{x^2}{1.001^x} \to 0.
- At x = 10^6, Pao’s: x^{1.2} \approx 1.585 \times 10^7 against x(\ln x)^2 \approx 1.909 \times 10^8. For all large x, Txawj’s, since \dfrac{x(\ln x)^2}{x^{1.2}} = \dfrac{(\ln x)^2}{x^{0.2}} \to 0.
- Compare natural logarithms. At x = 100: 30 \ln 100 \approx 138.2 against 100 \ln 2 \approx 69.3, so x^{30} is larger. At x = 300: 30 \ln 300 \approx 171.1 against 300 \ln 2 \approx 207.9, so 2^x is larger. 2^x grows faster, by the ladder.
- 0. With x = \dfrac{1}{u}, \displaystyle \sqrt{x}\, \ln x = -\dfrac{\ln u}{u^{1/2}} \to 0 as u \to \infty.
- 1. x^{1/x} = e^{(\ln x)/x}, the exponent goes to 0 by the ladder, and e^u is continuous, so the limit is e^0 = 1.
- 0. With x = -u, x^2 e^x = \dfrac{u^2}{e^u} \to 0 as u \to \infty.
- \dfrac{h}{f} = \dfrac{h}{g} \cdot \dfrac{g}{f}. The first factor goes to 0, the second to \dfrac{1}{L}, a number, so the product goes to 0 \cdot \dfrac{1}{L} = 0, and f grows faster than h.
- \dfrac{\log_2 x}{\ln x} = \dfrac{1}{\ln 2} is a positive constant, so the logarithms grow at the same rate. But \dfrac{e^x}{2^x} = \left(\dfrac{e}{2}\right)^x \to \infty since \dfrac{e}{2} > 1: changing a logarithm’s base multiplies it by a constant, while changing an exponential’s base multiplies it by another exponential.
- Put x = s^2 with s > 0; then s \to \infty as x \to \infty, and \displaystyle \dfrac{x^p}{e^{\sqrt{x}}} = \dfrac{s^{2p}}{e^s} \to 0 by the ladder with power 2p > 0 and base e.
- x^{\ln x} = e^{(\ln x)^2}. Against x^p = e^{p \ln x}: the quotient is e^{(\ln x)^2 - p \ln x} = e^{\ln x\,(\ln x - p)}, and the exponent grows without bound, so the quotient goes to \infty. Against 2^x = e^{x \ln 2}: the exponent of the quotient is (\ln x)^2 - x \ln 2 = x\left(\dfrac{(\ln x)^2}{x} - \ln 2\right), and since \dfrac{(\ln x)^2}{x} \to 0 this goes to -\infty, so the quotient goes to 0.