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.