Video Transcript
In this video, we’ll learn how to
compare the rate of growth of functions. For example, take the functions 𝑓
of 𝑥 equals 𝑥 squared and 𝑔 of 𝑥 equals 𝑥. We can look at their graphs for 𝑥
greater than zero. And we can see that, initially as
𝑥 increases from zero, 𝑔 of 𝑥 is greater than 𝑓 of 𝑥. But at some point, 𝑓 of 𝑥 starts
to grow faster than 𝑔 of 𝑥 does and so overtakes 𝑔 of 𝑥 at 𝑥 equals one. Intuitively then, it feels that 𝑓
of 𝑥 grows faster than 𝑔 of 𝑥. But we’d like to turn this
intuition into a mathematically precise statement.
How do we do this? Well, the idea is that, for very
large values of 𝑥, 𝑓 of 𝑥 is much larger than 𝑔 of 𝑥. So 𝑓 of 𝑁 is much bigger than 𝑔
of 𝑁 for some really big number 𝑁. We can say that 𝑓 of 𝑁 is big
compared to 𝑔 of 𝑁, when the quotient 𝑓 of 𝑁 over 𝑔 of 𝑁 is large. But we have a problem here. We have to pick some big value of
𝑁. And how will we know if we picked a
value of 𝑁, which is big enough for our purposes? We get around this problem by using
limits. Instead of picking a single value
of 𝑥, which we called 𝑁, we consider the limit of 𝑓 of 𝑥 over 𝑔 of 𝑥 as 𝑥
approaches ∞.
Now, how do we decide if this limit
is large? Well, we say it’s large if its
value is ∞. Surely everyone can agree that if
this is the case, then the limit is large and hence that 𝑓 of 𝑥 grows faster than
𝑔 of 𝑥. We take this to be our
mathematically precise definition which captures the intuition of 𝑓 of 𝑥 growing
faster than 𝑔 of 𝑥. We say that 𝑓 of 𝑥 grows faster
than 𝑔 of 𝑥 if the limit of 𝑓 of 𝑥 over 𝑔 of 𝑥 as 𝑥 approaches ∞ is
∞. Sometimes, the term “dominates” is
also used. 𝑓 of 𝑥 dominates 𝑔 of 𝑥, if the
limit of 𝑓 of 𝑥 over 𝑔 of 𝑥 as 𝑥 approaches ∞ is ∞.
So what does this mean for our
functions 𝑓 of 𝑥 equals 𝑥 squared and 𝑔 of 𝑥 equals 𝑥? Well, the limit of 𝑓 of 𝑥 over 𝑔
of 𝑥 as 𝑥 approaches ∞ is the limit of 𝑥 squared over 𝑥 as 𝑥 approaches
∞. That’s just using the definitions
of 𝑓 of 𝑥 and 𝑔 of 𝑥. And we can simplify the fraction 𝑥
squared over 𝑥 is just 𝑥. So we have the limit of 𝑥 as 𝑥
approaches ∞, which is ∞. What do we conclude? Well, even though both 𝑓 of 𝑥 and
𝑔 of 𝑥 approach ∞ as 𝑥 approaches ∞, 𝑓 of 𝑥 equals 𝑥 squared
somehow grows faster than or dominates 𝑔 of 𝑥 equals 𝑥. This is what our definition tells
us. Let’s summarize this definition in
the form of the question.
If the limit of 𝑓 of 𝑥 over 𝑔 of
𝑥 as 𝑥 approaches ∞ is ∞, what do you notice about the growth rate
of 𝑓 of 𝑥 compared to 𝑔 of 𝑥 as 𝑥 approaches ∞?
This limit tells us that the
quotient 𝑓 of 𝑥 over 𝑔 of 𝑥 grows without bound as 𝑥 approaches ∞. And for the quotient 𝑓 of 𝑥 over
𝑔 of 𝑥 to grow without bound, the function 𝑓 of 𝑥 must be growing faster than 𝑔
of 𝑥. Our conclusion is, therefore, that
the growth rate of 𝑓 of 𝑥 is greater than that of 𝑔 of 𝑥 as 𝑥 approaches
∞. Another way of saying this is that
the function 𝑓 of 𝑥 dominates the function 𝑔 of 𝑥.
Let’s now see a related question
where the value of the limit is no longer ∞, but zero.
If the limit of 𝑓 of 𝑥 over 𝑔 of
𝑥 as 𝑥 approaches ∞ is zero, what do you notice about the growth rate of 𝑓
of 𝑥 compared to 𝑔 of 𝑥 as 𝑥 approaches ∞?
As the limit of this quotient is
zero, as 𝑥 approaches ∞, we can tell that the magnitude of the 𝑓 of 𝑥 over
𝑔 of 𝑥 is very small for large values of 𝑥. In fact, to show me that the
numerator 𝑓 of 𝑥 is not just identically zero, we can imagine the quotient 𝑓 of
𝑥 over 𝑔 of 𝑥 getting smaller and smaller, closer and closer to zero in magnitude
as 𝑥 increases. Now, it’s tempting to think that,
for this to happen, the function 𝑓 of 𝑥 itself must be getting closer and closer
to zero. But this is not the case.
For example, we could take 𝑓 of 𝑥
to be equal to 𝑥. This is a function that increases
without bound as 𝑥 increases. If we then take 𝑔 of 𝑥 to be 𝑥
squared, then the quotient 𝑓 of 𝑥 over 𝑔 of 𝑥 is 𝑥 over 𝑥 squared or one over
𝑥. And this does indeed get smaller
and smaller in magnitude as 𝑥 increases. The point isn’t that 𝑓 of 𝑥
itself is small or getting smaller, it’s that it is small compared to 𝑔 of 𝑥. And with the limit as 𝑥 tends to
∞, we think about this in terms of the growth rates. The growth rate of 𝑓 of 𝑥 is
smaller than that of 𝑔 of 𝑥 as 𝑥 approaches ∞. Even though the function 𝑓 of 𝑥
equals 𝑥 is growing as 𝑥 increases, it isn’t growing as fast as 𝑔 of 𝑥 equals 𝑥
squared. And so the limit of 𝑓 of 𝑥 over
𝑔 of 𝑥 is zero. This is then our answer.
We can also flip this around. Another way of saying that the
growth rate of 𝑓 of 𝑥 is smaller than that of 𝑔 of 𝑥 is to say that the growth
rate of 𝑔 of 𝑥 is greater than that of 𝑓 of 𝑥. We might like to confirm this by
finding the limit of 𝑔 of 𝑥 over 𝑓 of 𝑥 as 𝑥 approaches ∞. This is the limit of one over 𝑓 of
𝑥 over 𝑔 of 𝑥 as 𝑥 approaches ∞, which, working somewhat informally, is
one over the limit of 𝑓 of 𝑥 over 𝑔 of 𝑥 as 𝑥 approaches ∞. This limit on the denominator we
know is zero from the question. And what we can’t normally divide
by zero, in this particular occasion, it can be justified. And so we’re not completely wrong
to say that one over zero must be plus or minus ∞.
Again, this isn’t 100 percent
rigorous, but it points to the growth rate of 𝑔 of 𝑥 being greater than that of 𝑓
of 𝑥 as 𝑥 approaches ∞. And that’s just another way of
saying that the growth rate of 𝑓 of 𝑥 is smaller than that of the 𝑔 of 𝑥 as 𝑥
approaches ∞, which was our answer.
We’ve seen that if the limit of 𝑓
of 𝑥 over 𝑔 of 𝑥 as 𝑥 approaches ∞ is ∞, then 𝑓 of 𝑥 grows
faster than 𝑔 of 𝑥 or 𝑓 of 𝑥 dominates 𝑔 of 𝑥. If, however, the limit of 𝑓 of 𝑥
over 𝑔 of 𝑥 as 𝑥 approaches ∞ is zero, then 𝑓 of 𝑥 grows slower than 𝑔
of 𝑥. And it is 𝑔 of 𝑥 which dominates
𝑓 of 𝑥 instead. However, ∞ and zero are the
only possible values of this limit. What happens if the value of this
limit is some other real number 𝑎? Well, there’s nothing particularly
formal that we say here, but 𝑓 of 𝑥 and 𝑔 of 𝑥 grow at roughly the same
rate. You might think that the function
𝑓 of 𝑥 equals two 𝑥 grows much faster than 𝑔 of 𝑥 equals 𝑥. But in fact, there’s not really
much in it.
That factor of two is negligible
when compared to the infinite difference, or rather quotient, between the growth
rates of the quadratic function 𝑓 of 𝑥 equals 𝑥 squared and the linear function
𝑔 of 𝑥 equals 𝑥. It’s perhaps best to think about
this in terms of domination. It’s not enough for 𝑓 of 𝑥 simply
to be greater than 𝑔 of 𝑥. It has to completely dominate 𝑔 of
𝑥. That’s a much stronger
requirement. When we’re talking about
domination, a constant multiple isn’t enough to shift the balance. We can make this statement
precise. If 𝑓 of 𝑥 dominates 𝑔 of 𝑥,
then, for any positive real numbers 𝑎 and 𝑏, 𝑎 times 𝑓 of 𝑥 dominates 𝑏 times
𝑔 of 𝑥. This isn’t too hard to prove.
To prove that 𝑎 times 𝑓 of 𝑥
dominates 𝑏 times 𝑔 of 𝑥, we just need to prove that the limit of their quotient
as 𝑥 approaches ∞ is ∞. One of our laws of limits allows us
to take out the constant factor 𝑎 over 𝑏 from inside the limit. And we know what the limit of 𝑓 of
𝑥 over 𝑔 of 𝑥 is as 𝑥 approaches ∞. As 𝑓 of 𝑥 dominates 𝑔 of 𝑥,
this must be ∞. The constant factor 𝑎 over 𝑏
can’t do anything to make that ∞ any smaller. And so our limit is also
∞. And hence, 𝑎 times 𝑓 of 𝑥
dominates 𝑏 times 𝑔 of 𝑥. This means that not only does 𝑓 of
𝑥 equals 𝑥 squared to dominate 𝑔 of 𝑥 equals 𝑥, but also 𝑓 of 𝑥 equals
0.001𝑥 squared dominates 𝑔 of 𝑥 equals 99𝑥 and so on.
Now, up to this point in the video,
we’ve mostly seen examples involving linear and quadratic functions. If you know how to find the limit
at ∞ of a rational function, that’s a function which is the quotient of two
polynomials, then you’ll be able to show when one polynomial dominates another. However, we’d like to consider
nonpolynomial functions as well. And for that, it’s helpful to know
about L’Hôpital’s rule. Let’s see an example.
Evaluate the limit of 𝑥 squared
over 𝑒 to the 𝑥 as 𝑥 approaches ∞ using L’Hôpital’s rule.
We might try to evaluate this limit
by using the fact that the limit of a quotient of functions is a quotient of their
limits. So we get the limit of 𝑥 squared
as 𝑥 approaches ∞ over the limit of 𝑒 to the 𝑥 of the 𝑥 and 𝑥 approaches
∞. The problem is that the limit of 𝑥
squared as 𝑥 approaches ∞ is ∞ as is the limit of 𝑒 to the 𝑥 as 𝑥
approaches ∞. And so we get the indeterminate
form ∞ over ∞. This is why we need to use
L’Hôpital’s rule. L’Hôpital’s rule says that if the
quotient of limits, the limit of 𝑓 of 𝑥 as 𝑥 approaches 𝑎 over the limit of 𝑔
of 𝑥 as 𝑥 approaches 𝑎, gives an indeterminate form. That’s zero over zero or a positive
or negative ∞ over a positive or negative ∞. Then the limit of the quotient of
functions 𝑓 of 𝑥 over 𝑔 of 𝑥 as 𝑥 approaches 𝑎 is equal the limit of the
quotient of their derivatives 𝑓 prime of 𝑥 over 𝑔 prime of 𝑥 as 𝑥 approaches
𝑎.
Of course, this only works if 𝑓
and 𝑔 differentiable functions. But in our case, they are 𝑓 of 𝑥
is 𝑥 squared, which is differentiable, as of 𝑔 of 𝑥, which is 𝑒 to the 𝑥. With this choice of 𝑓 of 𝑥 and 𝑔
of 𝑥, we’ve already seen that the quotient to their limits gives the indeterminate
form ∞ over ∞. So L’Hôpital’s rule does apply. And hence, we can say that the
limit of the quotient of functions that we’re looking for is equal to the limit of
the quotient of their derivatives. 𝑓 of 𝑥 is 𝑥 squared, and so 𝑓
prime of 𝑥 is two 𝑥, its derivative. 𝑔 of 𝑥 is 𝑒 to the 𝑥, and its
derivative is also 𝑒 to the 𝑥. The exponential function 𝑒 to the
𝑥 has the property that its derivative is just itself.
Now, we can try to use the fact
that the limit of a quotient of functions is a quotient of their limits. What is the limit of two 𝑥 as 𝑥
approaches ∞. Well, as 𝑥 approaches ∞,
two 𝑥 does as well. And the same is true in the
denominator. The limit of 𝑒 to the 𝑥 as 𝑥
approaches ∞, as we’ve really seen, is also ∞. We have another indeterminate form
here, ∞ over ∞. You might think that we haven’t
actually made any progress by applying the L’Hôpital’s rule. But in fact, we have. And we can see this by applying the
L’Hôpital’s rule one more time. This time we’re applying it to the
limit of two 𝑥 over 𝑒 to the 𝑥 as 𝑥 approaches ∞. And hence, we take 𝑓 of 𝑥 to be
two 𝑥 and 𝑔 of 𝑥 to be 𝑒 to the 𝑥.
The derivative of two 𝑥 is two and
the derivative of 𝑒 to the 𝑥 is 𝑒 to the 𝑥. And so applying L’Hôpital’s rule a
second time, we get the limit of two over 𝑒 to the 𝑥 as 𝑥 approaches
∞. Now, we can use the fact that the
limit of a quotient is a quotient of the limits. The limit of two as 𝑥 approaches
∞ is just two, and the limit of 𝑒 to the 𝑥 as 𝑥 approaches ∞ is
∞. Two over ∞ isn’t an
indeterminate form, although it contains ∞, which isn’t itself a real
number. In the context of limits, we can
see that any real number over ∞ is zero. And so that’s the value of our
initial limit, the limit of 𝑥 squared over 𝑒 to the 𝑥 as 𝑥 approaches ∞
as well.
If you’re worried about saying that
two divided by ∞ is zero, then there’s another way of saying this. Instead of finding a quotient of
limits, we can think of the function two over 𝑒 to the 𝑥 or two 𝑒 to the negative
𝑥. You might recognize this as an
exponential decay, 𝑒 to the negative 𝑥. And hence, two times 𝑒 to the
negative 𝑥 approaches zero as 𝑥 approaches ∞. Either way, the answer is zero.
One way of interpreting the fact
that the limit of 𝑥 squared over 𝑒 to the 𝑥 as 𝑥 approaches ∞ is zero is
to say that the function 𝑥 squared grows more slowly than 𝑒 to the 𝑥 as 𝑥
approaches ∞. Or in other words, the function 𝑒
to the 𝑥 dominates the function 𝑥 squared. In fact by applying L’Hôpital’s
rule repeatedly, we can show that the exponential function 𝑒 to the 𝑥 dominates
any polynomial function.
With a polynomial of degree 𝑛 in
the numerator, applying L’Hôpital’s rule once, we differentiate this numerator and
get a polynomial of degree 𝑛 minus one. By repeatedly applying L’Hôpital’s
rule, we can reduce the degree of the polynomial in the numerator until it’s just a
constant, a polynomial of degree zero. And we know that the limit of a
constant over 𝑒 to the 𝑥 or, equivalently, a constant times 𝑒 to the negative 𝑥
as 𝑥 approaches ∞ is zero. 𝑒 to the 𝑥, therefore, dominates
all polynomials.
This fact is one of the
cornerstones of computational complexity in computer science. If the time it takes an algorithm
to run is a polynomial function of the length of its input, then that algorithm is
considered to be quite fast. If, however, the time taken is an
exponential function of the length of the inputs to the algorithm, then that
algorithm is considered to be slow. The concept of computational
complexity is beyond the scope of this video, but I’d recommend that you look into
it yourself, as it is a highly important concept and is directly related to the
topic of comparing the growth of functions.
Let’s now finish by summarizing
what we’ve learned. We say that the function 𝑓 of 𝑥
dominates the function 𝑔 of 𝑥. If the limit of 𝑓 of 𝑥 over 𝑔 of
𝑥 as 𝑥 approaches ∞ is ∞. In this case, we may also say that
the growth rate of 𝑓 of 𝑥 is greater than that of 𝑔 of 𝑥 as 𝑥 approaches
∞. If the limit of 𝑓 of 𝑥 over 𝑔 of
𝑥 as 𝑥 approaches ∞ is zero, then it is 𝑔 of 𝑥, which dominates 𝑓 of
𝑥. In the remaining possibility where
the limit of 𝑓 of 𝑥 over 𝑔 of 𝑥 is some nonzero real number 𝑎, then neither
function dominates the other. The exponential function 𝑒 to the
𝑥 dominates all polynomial functions. This fact and the concepts of
comparing the growth of functions more generally, formally cornerstone of
computational complexity, are very important topic in computer science.
