WEBVTT
00:00:00.410 --> 00:00:04.240
In this video, weβll learn how to compare the rate of growth of functions.
00:00:05.100 --> 00:00:10.090
For example, take the functions π of π₯ equals π₯ squared and π of π₯ equals π₯.
00:00:10.930 --> 00:00:13.680
We can look at their graphs for π₯ greater than zero.
00:00:14.370 --> 00:00:19.730
And we can see that, initially as π₯ increases from zero, π of π₯ is greater than π of π₯.
00:00:20.280 --> 00:00:27.700
But at some point, π of π₯ starts to grow faster than π of π₯ does and so overtakes π of π₯ at π₯ equals one.
00:00:28.410 --> 00:00:32.620
Intuitively then, it feels that π of π₯ grows faster than π of π₯.
00:00:33.170 --> 00:00:37.220
But weβd like to turn this intuition into a mathematically precise statement.
00:00:38.170 --> 00:00:39.210
How do we do this?
00:00:39.470 --> 00:00:45.270
Well, the idea is that, for very large values of π₯, π of π₯ is much larger than π of π₯.
00:00:45.990 --> 00:00:50.950
So π of π is much bigger than π of π for some really big number π.
00:00:51.760 --> 00:00:58.360
We can say that π of π is big compared to π of π, when the quotient π of π over π of π is large.
00:00:59.090 --> 00:01:00.290
But we have a problem here.
00:01:00.550 --> 00:01:02.740
We have to pick some big value of π.
00:01:02.990 --> 00:01:07.520
And how will we know if we picked a value of π, which is big enough for our purposes?
00:01:08.370 --> 00:01:10.780
We get around this problem by using limits.
00:01:11.570 --> 00:01:19.280
Instead of picking a single value of π₯, which we called π, we consider the limit of π of π₯ over π of π₯ as π₯ approaches β.
00:01:20.320 --> 00:01:23.080
Now, how do we decide if this limit is large?
00:01:23.900 --> 00:01:27.350
Well, we say itβs large if its value is β.
00:01:28.040 --> 00:01:36.800
Surely everyone can agree that if this is the case, then the limit is large and hence that π of π₯ grows faster than π of π₯.
00:01:37.420 --> 00:01:44.880
We take this to be our mathematically precise definition which captures the intuition of π of π₯ growing faster than π of π₯.
00:01:45.730 --> 00:01:53.650
We say that π of π₯ grows faster than π of π₯ if the limit of π of π₯ over π of π₯ as π₯ approaches β is β.
00:01:54.430 --> 00:01:57.320
Sometimes, the term βdominatesβ is also used.
00:01:57.490 --> 00:02:03.840
π of π₯ dominates π of π₯, if the limit of π of π₯ over π of π₯ as π₯ approaches β is β.
00:02:04.830 --> 00:02:10.170
So what does this mean for our functions π of π₯ equals π₯ squared and π of π₯ equals π₯?
00:02:11.010 --> 00:02:19.060
Well, the limit of π of π₯ over π of π₯ as π₯ approaches β is the limit of π₯ squared over π₯ as π₯ approaches β.
00:02:19.280 --> 00:02:22.480
Thatβs just using the definitions of π of π₯ and π of π₯.
00:02:23.130 --> 00:02:28.070
And we can simplify the fraction π₯ squared over π₯ is just π₯.
00:02:28.780 --> 00:02:35.200
So we have the limit of π₯ as π₯ approaches β, which is β.
00:02:36.280 --> 00:02:37.580
What do we conclude?
00:02:38.320 --> 00:02:49.100
Well, even though both π of π₯ and π of π₯ approach β as π₯ approaches β, π of π₯ equals π₯ squared somehow grows faster than or dominates π of π₯ equals π₯.
00:02:49.930 --> 00:02:52.230
This is what our definition tells us.
00:02:52.990 --> 00:02:55.960
Letβs summarize this definition in the form of the question.
00:02:56.830 --> 00:03:06.600
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 β?
00:03:07.890 --> 00:03:14.630
This limit tells us that the quotient π of π₯ over π of π₯ grows without bound as π₯ approaches β.
00:03:15.270 --> 00:03:22.720
And for the quotient π of π₯ over π of π₯ to grow without bound, the function π of π₯ must be growing faster than π of π₯.
00:03:23.510 --> 00:03:30.440
Our conclusion is, therefore, that the growth rate of π of π₯ is greater than that of π of π₯ as π₯ approaches β.
00:03:31.340 --> 00:03:35.870
Another way of saying this is that the function π of π₯ dominates the function π of π₯.
00:03:36.800 --> 00:03:43.630
Letβs now see a related question where the value of the limit is no longer β, but zero.
00:03:44.710 --> 00:03:55.250
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 β?
00:03:56.250 --> 00:04:05.780
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 π₯.
00:04:06.380 --> 00:04:18.540
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.
00:04:20.000 --> 00:04:26.220
Now, itβs tempting to think that, for this to happen, the function π of π₯ itself must be getting closer and closer to zero.
00:04:26.960 --> 00:04:28.430
But this is not the case.
00:04:29.210 --> 00:04:32.130
For example, we could take π of π₯ to be equal to π₯.
00:04:33.020 --> 00:04:36.710
This is a function that increases without bound as π₯ increases.
00:04:37.420 --> 00:04:46.580
If we then take π of π₯ to be π₯ squared, then the quotient π of π₯ over π of π₯ is π₯ over π₯ squared or one over π₯.
00:04:46.840 --> 00:04:51.180
And this does indeed get smaller and smaller in magnitude as π₯ increases.
00:04:51.940 --> 00:04:58.700
The point isnβt that π of π₯ itself is small or getting smaller, itβs that it is small compared to π of π₯.
00:04:59.550 --> 00:05:04.160
And with the limit as π₯ tends to β, we think about this in terms of the growth rates.
00:05:04.330 --> 00:05:09.780
The growth rate of π of π₯ is smaller than that of π of π₯ as π₯ approaches β.
00:05:10.720 --> 00:05:18.040
Even though the function π of π₯ equals π₯ is growing as π₯ increases, it isnβt growing as fast as π of π₯ equals π₯ squared.
00:05:18.260 --> 00:05:21.670
And so the limit of π of π₯ over π of π₯ is zero.
00:05:22.390 --> 00:05:24.090
This is then our answer.
00:05:24.920 --> 00:05:26.640
We can also flip this around.
00:05:27.250 --> 00:05:35.130
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 π₯.
00:05:36.120 --> 00:05:41.180
We might like to confirm this by finding the limit of π of π₯ over π of π₯ as π₯ approaches β.
00:05:42.140 --> 00:05:53.700
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 β.
00:05:54.480 --> 00:05:58.360
This limit on the denominator we know is zero from the question.
00:05:59.490 --> 00:06:04.610
And what we canβt normally divide by zero, in this particular occasion, it can be justified.
00:06:04.710 --> 00:06:09.190
And so weβre not completely wrong to say that one over zero must be plus or minus β.
00:06:10.200 --> 00:06:17.890
Again, this isnβt 100 percent rigorous, but it points to the growth rate of π of π₯ being greater than that of π of π₯ as π₯ approaches β.
00:06:18.710 --> 00:06:26.010
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.
00:06:26.980 --> 00:06:36.500
Weβve seen that if the limit of π of π₯ over π of π₯ as π₯ approaches β is β, then π of π₯ grows faster than π of π₯ or π of π₯ dominates π of π₯.
00:06:37.330 --> 00:06:45.030
If, however, the limit of π of π₯ over π of π₯ as π₯ approaches β is zero, then π of π₯ grows slower than π of π₯.
00:06:45.290 --> 00:06:48.280
And it is π of π₯ which dominates π of π₯ instead.
00:06:49.430 --> 00:06:53.850
However, β and zero are the only possible values of this limit.
00:06:55.000 --> 00:06:58.590
What happens if the value of this limit is some other real number π?
00:06:59.550 --> 00:07:06.250
Well, thereβs nothing particularly formal that we say here, but π of π₯ and π of π₯ grow at roughly the same rate.
00:07:07.200 --> 00:07:12.140
You might think that the function π of π₯ equals two π₯ grows much faster than π of π₯ equals π₯.
00:07:12.380 --> 00:07:14.350
But in fact, thereβs not really much in it.
00:07:15.190 --> 00:07:26.670
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 π₯.
00:07:27.610 --> 00:07:30.830
Itβs perhaps best to think about this in terms of domination.
00:07:31.150 --> 00:07:34.750
Itβs not enough for π of π₯ simply to be greater than π of π₯.
00:07:34.890 --> 00:07:37.530
It has to completely dominate π of π₯.
00:07:38.180 --> 00:07:40.200
Thatβs a much stronger requirement.
00:07:40.990 --> 00:07:45.710
When weβre talking about domination, a constant multiple isnβt enough to shift the balance.
00:07:46.640 --> 00:07:48.550
We can make this statement precise.
00:07:49.360 --> 00:07:56.780
If π of π₯ dominates π of π₯, then, for any positive real numbers π and π, π times π of π₯ dominates π times π of π₯.
00:07:57.720 --> 00:07:59.660
This isnβt too hard to prove.
00:08:00.470 --> 00:08:07.910
To prove that π times π of π₯ dominates π times π of π₯, we just need to prove that the limit of their quotient as π₯ approaches β is β.
00:08:08.670 --> 00:08:13.590
One of our laws of limits allows us to take out the constant factor π over π from inside the limit.
00:08:14.580 --> 00:08:18.990
And we know what the limit of π of π₯ over π of π₯ is as π₯ approaches β.
00:08:19.720 --> 00:08:23.840
As π of π₯ dominates π of π₯, this must be β.
00:08:24.590 --> 00:08:29.540
The constant factor π over π canβt do anything to make that β any smaller.
00:08:30.390 --> 00:08:32.570
And so our limit is also β.
00:08:32.950 --> 00:08:36.200
And hence, π times π of π₯ dominates π times π of π₯.
00:08:37.050 --> 00:08:50.040
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.
00:08:50.990 --> 00:08:56.360
Now, up to this point in the video, weβve mostly seen examples involving linear and quadratic functions.
00:08:57.040 --> 00:09:06.580
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.
00:09:07.340 --> 00:09:10.310
However, weβd like to consider nonpolynomial functions as well.
00:09:10.450 --> 00:09:13.320
And for that, itβs helpful to know about LβHΓ΄pitalβs rule.
00:09:14.420 --> 00:09:15.450
Letβs see an example.
00:09:16.650 --> 00:09:23.270
Evaluate the limit of π₯ squared over π to the π₯ as π₯ approaches β using LβHΓ΄pitalβs rule.
00:09:24.170 --> 00:09:29.690
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.
00:09:30.600 --> 00:09:36.560
So we get the limit of π₯ squared as π₯ approaches β over the limit of π to the π₯ of the π₯ and π₯ approaches β.
00:09:37.430 --> 00:09:44.860
The problem is that the limit of π₯ squared as π₯ approaches β is β as is the limit of π to the π₯ as π₯ approaches β.
00:09:45.670 --> 00:09:48.900
And so we get the indeterminate form β over β.
00:09:49.680 --> 00:09:52.300
This is why we need to use LβHΓ΄pitalβs rule.
00:09:53.280 --> 00:10:02.010
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.
00:10:02.470 --> 00:10:07.650
Thatβs zero over zero or a positive or negative β over a positive or negative β.
00:10:08.270 --> 00:10:18.100
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 π.
00:10:18.840 --> 00:10:22.320
Of course, this only works if π and π differentiable functions.
00:10:22.320 --> 00:10:29.850
But in our case, they are π of π₯ is π₯ squared, which is differentiable, as of π of π₯, which is π to the π₯.
00:10:30.790 --> 00:10:37.640
With this choice of π of π₯ and π of π₯, weβve already seen that the quotient to their limits gives the indeterminate form β over β.
00:10:37.970 --> 00:10:39.860
So LβHΓ΄pitalβs rule does apply.
00:10:40.760 --> 00:10:46.840
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.
00:10:47.610 --> 00:10:52.650
π of π₯ is π₯ squared, and so π prime of π₯ is two π₯, its derivative.
00:10:53.550 --> 00:10:58.010
π of π₯ is π to the π₯, and its derivative is also π to the π₯.
00:10:58.930 --> 00:11:03.310
The exponential function π to the π₯ has the property that its derivative is just itself.
00:11:04.040 --> 00:11:08.660
Now, we can try to use the fact that the limit of a quotient of functions is a quotient of their limits.
00:11:09.420 --> 00:11:12.010
What is the limit of two π₯ as π₯ approaches β.
00:11:12.260 --> 00:11:14.950
Well, as π₯ approaches β, two π₯ does as well.
00:11:15.780 --> 00:11:17.800
And the same is true in the denominator.
00:11:17.950 --> 00:11:22.790
The limit of π to the π₯ as π₯ approaches β, as weβve really seen, is also β.
00:11:24.280 --> 00:11:27.330
We have another indeterminate form here, β over β.
00:11:28.010 --> 00:11:31.590
You might think that we havenβt actually made any progress by applying the LβHΓ΄pitalβs rule.
00:11:31.680 --> 00:11:32.870
But in fact, we have.
00:11:32.950 --> 00:11:36.040
And we can see this by applying the LβHΓ΄pitalβs rule one more time.
00:11:36.910 --> 00:11:41.580
This time weβre applying it to the limit of two π₯ over π to the π₯ as π₯ approaches β.
00:11:42.330 --> 00:11:47.560
And hence, we take π of π₯ to be two π₯ and π of π₯ to be π to the π₯.
00:11:49.240 --> 00:11:54.530
The derivative of two π₯ is two and the derivative of π to the π₯ is π to the π₯.
00:11:55.180 --> 00:12:01.300
And so applying LβHΓ΄pitalβs rule a second time, we get the limit of two over π to the π₯ as π₯ approaches β.
00:12:02.120 --> 00:12:05.640
Now, we can use the fact that the limit of a quotient is a quotient of the limits.
00:12:06.340 --> 00:12:14.350
The limit of two as π₯ approaches β is just two, and the limit of π to the π₯ as π₯ approaches β is β.
00:12:15.240 --> 00:12:21.100
Two over β isnβt an indeterminate form, although it contains β, which isnβt itself a real number.
00:12:21.290 --> 00:12:25.920
In the context of limits, we can see that any real number over β is zero.
00:12:26.650 --> 00:12:33.130
And so thatβs the value of our initial limit, the limit of π₯ squared over π to the π₯ as π₯ approaches β as well.
00:12:33.880 --> 00:12:38.530
If youβre worried about saying that two divided by β is zero, then thereβs another way of saying this.
00:12:39.260 --> 00:12:45.540
Instead of finding a quotient of limits, we can think of the function two over π to the π₯ or two π to the negative π₯.
00:12:46.160 --> 00:12:49.480
You might recognize this as an exponential decay, π to the negative π₯.
00:12:49.480 --> 00:12:53.930
And hence, two times π to the negative π₯ approaches zero as π₯ approaches β.
00:12:55.800 --> 00:12:57.660
Either way, the answer is zero.
00:12:58.900 --> 00:13:11.030
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 β.
00:13:11.740 --> 00:13:16.130
Or in other words, the function π to the π₯ dominates the function π₯ squared.
00:13:16.980 --> 00:13:23.880
In fact by applying LβHΓ΄pitalβs rule repeatedly, we can show that the exponential function π to the π₯ dominates any polynomial function.
00:13:24.710 --> 00:13:32.810
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.
00:13:33.380 --> 00:13:40.830
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.
00:13:41.490 --> 00:13:50.020
And we know that the limit of a constant over π to the π₯ or, equivalently, a constant times π to the negative π₯ as π₯ approaches β is zero.
00:13:51.530 --> 00:13:54.360
π to the π₯, therefore, dominates all polynomials.
00:13:55.250 --> 00:13:59.510
This fact is one of the cornerstones of computational complexity in computer science.
00:14:00.270 --> 00:14:07.490
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.
00:14:08.360 --> 00:14:15.180
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.
00:14:16.000 --> 00:14:28.680
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.
00:14:29.390 --> 00:14:31.670
Letβs now finish by summarizing what weβve learned.
00:14:32.690 --> 00:14:36.370
We say that the function π of π₯ dominates the function π of π₯.
00:14:36.500 --> 00:14:41.180
If the limit of π of π₯ over π of π₯ as π₯ approaches β is β.
00:14:42.000 --> 00:14:48.420
In this case, we may also say that the growth rate of π of π₯ is greater than that of π of π₯ as π₯ approaches β.
00:14:49.390 --> 00:14:56.410
If the limit of π of π₯ over π of π₯ as π₯ approaches β is zero, then it is π of π₯, which dominates π of π₯.
00:14:57.440 --> 00:15:04.890
In the remaining possibility where the limit of π of π₯ over π of π₯ is some nonzero real number π, then neither function dominates the other.
00:15:05.640 --> 00:15:09.210
The exponential function π to the π₯ dominates all polynomial functions.
00:15:10.120 --> 00:15:19.090
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.