Video: Comparing Rate of Growth of Functions

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.