2.5「Stanford Algorithms」ASYMPTOT

This video is for those of you who want some additional practice with asymptotic notation.

And we're gonna go through three additional optional examples.

Let's start with the first one.

So the point of this first example is to show how to formally prove that one function is big O of another.

So the function that I want to work with is two raised to the N plus ten, okay, so it's the two to the N function that you're all familiar with, we're going to shift it by ten and the claim is that this function is big O of two to the N, so without the ten.

So how would one prove such a claim? Well lets go back to the definition of what it means for one function to be big O over another, what we have to prove is we need to show that there exists two constants, so that for all sufficiently large N meaning N bigger than N-nought, our left hand side, so the function should be N plus ten is bounded above by a constant multiple C times the function on right hand side to the N.

Right so for all sufficiently large N the function is bounded above by a constant multiple of two to the N.

So unlike the first basic example where I just pulled the two constants out of a hat let's actually start the proof and see how you'd reverse engineer the suitable choice of these two constants.

So, what a proof would look like, it would start with two to the N plus ten, on the left-hand side, and then there'd be a chain of inequalities, terminating in this, C times two to the N.

So, let's just go ahead and start such a proof, and see what we might do.

So, if we start with two to the N plus ten on the left-hand side, what would our first step look like? Well, this 10's really annoying, so it makes sense to separate it out.

So you could write two to the N plus ten as the product of two terms.

Two to the ten, and then the two to the N.

Also known as just 1024 times two to the N.

And now we're in, looking in really good shape.

So if you look at where we are so far, and where we want to get to, it seems like we should be choosing our constant C to be 1024.

So if we choose C to be 1024 and we don't have to be clever with N-nought we can just set that equal to one, then indeed star holds to the desired inequality and remember to prove that one function is big O of another all you gotta do is come up with one pair of constants that works and we've just reverse engineered it just choosing the constant C to be 1024 and N-nought to be one works so this proves that two to the N plus ten is big O over two to the N.

Next let's turn to another non example how, of a function which is not big O over another.

And so this will look superficially similar to the previous one.

Instead of taking, adding ten in the exponent of the function two to the N, I'm gonna multiply by ten in the exponent.

And the claim is if you multiply by ten in the exponent then this is not the same asymptotically as two to the N.

So once again, usually the way you prove one thing is not big O of another is by contridiction.

So we're going to assume the contrary, that two to the ten N is in fact big O of two to the N.

What would it mean if that were true? Well, by the definition of big O notation, that would mean there are constant C and N-nought.

So that for all large N, two to the ten N is bounded above by C times 2 to the N.

So to complete the proof what we have to do is go from this assumption and derive something which is obviously false but that's easy to do just by cancelling this 2 of the N terms from both sides.

So if we divide both sides by 2 to the N, which is a positive number since N is positive, what we find would be a logical consequence of our assumption would be that two raised to the nine N is bounded above by some fixed constant C for all N at least N-nought.

But this inequality of course is certainly false.

The right hand side is some fixed constant independent of N.

The left hand side is going to infinity as N grows large.

So there's no way this inequality holds for arbitrarily large N.

So that concludes the proof by contradiction.

This means our assumption was not the case, and indeed it is not the case that two to the ten N is big O of two to the N.

So our third and final example is a little bit more complicated than the first two.

It'll give us some practice using theta notation.

Recall that while big O is analogous to saying one function is less than or equal to another, theta notation is in the spirit of saying one function is equal asymptotically to another.

So here's gonna be the formal claim we're gonna prove, for every pair of functions F and G, both of these functions are defined on the positive integers, the claim is that it doesn't matter, up to a constant factors, whether we take point wise maximum of the two functions or whether we take the point wise sum of the two functions.

So let me make sure it's clear that you know I mean by the point wise maximum by max F and G.

So, if you look at the two functions, both functions of N, maybe we have F being this green function here and we have g hooked to this red function.

Then by the point wise maximum max(F,G) just means the upper envelope of these two functions.

So that's gonna be this blue function.

So lets now turn to the proof of this claim that the point wise function of these two function is theta of the sum of two functions.

So let's recall what theta means formally.

What it means is that the function on the left can be sandwiched between the constant multiples of the function on the right.

So we need to exhibit both the usual N-nought but also two constants, the small one, C1, and the big one, C2, so that the point wise maximum(F,G), whatever that may be, is wedged in between C1 and C2 times F(N) plus G(N), respectively.

So to see where these constants C1 and C2 are going to come from, let's observe the following inequalities.

So no matter what N is, any positive integer N, we have the following.

Suppose we take the larger of F of N and G of N.

And remember now, we've fixed the value of N, and it's just some integer, you know, like 23.

And now F of N and G of N are theirselves, just numbers.

You know, maybe they're 57 and 74, or whatever.

And if you take the larger of F of N and G of N, that's certainly no more than the sum of F of N plus G of N.

Now, I'm using, in this inequality, that F and G are positive.

And that's something I've been assuming throughout the course so far.

Here, I wanna be explicit about it, we're assuming that F and G cannot output negative numbers.

Whatever integer you feed in, you get out something positive.

Now, the functions we care about are things like the running time of algorithms, so there's really no reason for us to pollute our thinking with negative numbers.

So, we're just gonna always be assuming in this class, positive numbers.

And I'm actually using it here, the right hand side is the sum of two things, is bigger than just either one of the constituent summants.

Secondly.

If we double the larger of F of N and G of N well that's going to exceed the sum of F of N plus G of N, right? Because on the right hand side we have a big number plus a small number and then on the left hand side we have two copies of the big number so that is going to be something larger, now it's gonna be convenient it's gonna be more obvious what's going on if I divide both of these sides by two so that the maximum of F of N and G of N is at least half of F of N plus G of N that is at least half of the average and now we're pretty much home free right so what does this say.

This says that for every possible N, the maximums wedged between suitable multiples of the sum.

So one-half of F of N plus G of N.

There's a lower bound on the maximum.

This is just the second inequality that we derived.

And by the first inequality that's bounded above by once times the sum.

And this holds no matter what N is, [inaudible] at least one.

And this is exactly what it means to prove that one function is theta of another.

We've shown that for all N, not just for insuffiently large, but in fact for all N.

The pointwise maximum of F and G is wedged between suitable constant multiples of their sum.

And again, just to be explicit, the certifying choices of constants are N-nought equals one.

The smaller constant is one half.

And the bigger constant equals one.

And that completes the proof.

该视频适合那些想要一些渐近符号练习的人。

我们将介绍另外三个可选示例。

让我们从第一个开始。

因此，第一个示例的重点是说明如何正式证明一个函数是另一个函数的大O。

所以我要使用的函数是将两个加到N加10，好吧，所以这是大家都熟悉的N函数的两个，我们将其移动十，并且声称此功能是N的两个大O，所以没有十。

那么，如何证明这一主张呢？好，让我们回到定义上，对于一个函数来说，大一个O对另一个函数意味着什么，我们必须证明的是，我们需要证明存在两个常数，因此对于所有足够大的N来说，N都大于N-没有，我们的左手边，因此该函数应为N加10，其上限是C乘以C的右手边对N的常数倍。

正确，因此对于所有足够大的N，该函数在上方均以N的2的恒定倍数为边界。

因此，与第一个基本示例不同，我只是从帽子中拉出了两个常量，让我们实际开始验证，看看如何对这两个常量进行适当选择。

因此，证明将是什么样的，它从左侧的2到N加10开始，然后是一串不等式，终止于此，C等于N的2倍。

因此，让我们继续进行这样的证明，看看我们会做什么。

因此，如果我们从左侧的2到N加10开始，第一步是什么样的？好吧，这个10确实很烦人，因此将其分开是有意义的。

因此，您可以在N加10上写两个，作为两个项的乘积。

二到十，然后二到N。

也称为N的1024倍。

现在我们进入了，看起来真的很好。

因此，如果您查看目前为止的位置以及想要到达的位置，似乎我们应该将常量C选择为1024。

因此，如果我们选择C为1024，而不必对N取整，那么我们可以将其设置为等于1，那么星形确实满足所需的不等式，并记住证明一个函数是另一个函数的大O您要做的就是拿出一对有效的常数，我们只是对其进行了逆向工程，只需选择常数C为1024，而N则不应为一个常数，这证明N加上10的两个常数很大O超过N的两倍。

接下来，让我们转到另一个非示例性的函数，该函数与另一个函数相比并不大。

因此，从表面上看，这看起来类似于上一个。

与其将函数2的指数乘以10，不取N，我要乘以10。

要求是如果您将指数乘以10，那么与N的2渐近地不同。

因此，再次重申，通常，您证明一件事对另一件事不大的方法是出于矛盾。

因此，我们要假设相反，N的2到10实际上是N的2的大O。

如果那是真的，那意味着什么？好吧，根据大O表示法的定义，这意味着C和N为常数。

因此，对于所有大的N，上面的C乘以2等于N，则十个N中有两个。

因此，要完成证明，我们要做的就是从这个假设中得出显然是错误的东西，但这很容易做到，只需从双方取消N个条件中的这两个条件即可。

因此，如果我们将两边都除以2，则N就是一个正数，因为N是正数，所以我们得出的逻辑结论是，假设升到9 N的两个以某个固定常数C为界对于所有的N，至少N个没有。

但是这种不平等当然是错误的。

右侧是一些独立于N的固定常数。

随着N的增大，左侧将变为无穷大。

因此，对于任意大的N来说，这种不平等是不可能的。

这样就可以得出矛盾的证明。

这意味着我们的假设并非如此，事实上，并非十个二的N是二个N的大O。

因此，我们的第三个也是最后一个示例要比前两个复杂一些。

它将为我们提供一些使用theta表示法的实践。

回想一下，虽然大O类似于说一个函数小于或等于另一个函数，但theta表示法的精神是说一个函数渐近等于另一个函数。

因此，这将是我们要证明的正式声明，对于每对函数F和G，这两个函数都是在正整数上定义的，它的声明是无关紧要的，直到一个恒定因子，是否我们取两个函数的逐点最大值，或者我们取两个函数的逐点求和。

因此，请确保您清楚我的意思是最大F和G的逐点最大值。

因此，如果您查看两个函数，即N的两个函数，也许我们这里的F是这个绿色函数，而我们已经将g挂接到了这个红色函数。

然后，逐点最大值max（F，G）仅表示这两个函数的上限。

这就是蓝色功能。

因此，现在让我们来证明这一主张的证明：这两个函数的逐点函数是两个函数之和的θ。

因此，让我们回顾一下theta的正式含义。

这意味着左侧的函数可以夹在右侧函数的常数倍之间。

因此，我们既需要展示通常的N值，又要展示两个常数，小常数C1和大常数C2，以便将逐点最大值（F，G）楔入其中C1和C2分别乘以F（N）加G（N）。

因此，要查看这些常数C1和C2的来源，让我们观察以下不等式。

因此，无论N是多少，任何正整数N，我们都有以下内容。

假设我们取N中的F和N中的G中的较大者。

记住，我们已经固定了N的值，它只是一个整数，例如23。

现在N的F和N的G本身就是数字。

您知道，也许他们分别是57岁和74岁​​。

而且，如果采用N的F和N的G中的较大者，那肯定不超过N的F与N的G之和。

现在，在这种不等式中，我使用F和G为正。

到目前为止，我一直在假设这一点。

在这里，我想明确一点，我们假设F和G无法输出负数。

无论输入什么整数，都会得到一些积极的结果。

现在，我们关心的功能是算法的运行时间，因此我们实际上没有理由用负数来污染我们的思维。

因此，我们将始终在这一堂课中假设正数。

我实际上在这里使用它，右侧是两件事的总和，比任何一个组成的总和都大。

其次。

如果我们将N的F和N的G中的较大者加倍，那将超过N的F和N的G之和，对吗？因为在右侧，我们有一个大数字加一个小数字，然后在左侧，我们有两个大数字的副本，所以这将是一个更大的数字，现在它将很方便，它将变得更加明显如果我将这两边都除以2，那么N的F的最大值和N的G的最大值至少是N的F的一半加上N的G的平均值至少是平均值的一半，那么我们就差不多了家庭自由权，这是什么意思。

这就是说，对于每个可能的N，最大值楔入总和的合适倍数之间。

因此，N的F的一半加上N的G的一半。

最大值有一个下限。

这只是我们得出的第二个不平等。

而且，第一个不等式的总和是上述和的一倍。

不管N是多少，[听不清]至少一个都成立。

这正是证明一个函数是另一函数的θ的含义。

我们已经表明，对于所有N，不仅对于不足够大的，而且对于所有N。

F和G的逐点最大值被楔入它们的和的合适常数倍之间。

再一次，为了明确起见，常数的证明选择是N-nought等于1。

较小的常数是一半。

而较大的常数等于1。

这样就完成了证明。