Video 2-4: Asymptotic Pitfalls

0:04 I have one more last caveat and for that um a small example. First of all um here's a little algorithm to compute an integer power. So some some number x and I want to raise it to a power and the exponent is an integer. Of course, you know what this means, but how would you compute this if these numbers are fairly large? Uh, one way to do it is is written here in a slightly funny way. I'm I'm assuming that you give me the binary representation of this exponent. So, it comes as the the bits of the exponent written in binary. And then I can do this repeated doubling trick. So um I start with result being one and then whenever the bit in the exponent starting with the least significant one is a one I multiply the result by my base um sorry I always multiply I always square the result this is multiply with itself and if the bit is one I multiply my x in and it turns out this gives you the right answer for all values of m.

1:26 Um for example, say you want to raise x to the fifth power. Five in binary is this four and one. So I would start with one and um I would square one. Well, that turns one into one. And then because the last bit is set, I would multiply this by X. Um, so I get X as my result. Now I move to the next bit. The next bit is a zero bit, this middle one. So I would square X but not multiply by another X. I just leave it as is.

2:24 And then I look at the last digit of my exponent. That's a one again. So I would square this first, but then also multiply by another x. And so it turns out to be x to the 5th. [snorts] That's a way to compute exponents. It's a bit besides the point. I just thought it's useful to have a concrete example so that you see this weird thing that I'm about to show you actually arises in in algorithms. Suppose you wanted to determine how costly this algorithm is. Maybe you have a different algorithm where you say um x to the 5th I can also compute by xx and x five times and maybe that's better or worse. So let's analyze this algorithm and let's say our elementary operation is the number of multiplications which um you do at two points in the code here and here. The first one is easy to count. You do this or each iteration of this loop and the loop is iterated n times if you have n bits.

3:31 That's the assumption that we give this exponent in binary and it has n bits. So this line four will contribute n multiplications either way no matter what the input is. And then the line here line five has an if in front. So I'm only getting a multiplication for the one bits in m. That's what's written here. So clearly my uh number of multiplications is always between n and 2 n. Okay.

4:01 [snorts] Now what can you say about this asmtoically? Uh maybe let's let's briefly do this. Um I'll show you the algorithm again. So just type in some some text to show uh what you think and I'm going to show the answers right away.

4:31 I think this question tests two things. Whether you're still with me despite all the detour with this algorithm, you know what to do. It's uh it's easy, but it also tests something about the asmtoic notation.

4:52 Now remember the question is what's the most precise statement? Meaning anything you're you're uh not stating should be true in a way. more people are typing but there's a certain tendency for the answer is theta and uh what is not so visible here four people said theta the rest is one so it's it's blowing up the proportion a little So is the majority correct? First of all, let's check let's check this in two in two ways. First of all, C is lower and upper bounded by N times a certain constant. That is precisely what theta means in intuitive terms. I could also say I'm taking C and divide by N. you want to be systematic and now I could uh upper and lower bound this quotient of course the same thing happens so it's bounded from above and below which means c is in theta of n now the question is is this correct in the sense that it's the most precise statement you can make here and that is maybe a bit nonobvious but in this case um it is because the actual cost C has a strange behavior as a function of of um m and um so as a function of m all you can say is theta of log m but it uh wobbles around because the number of ones in the binary representation is a rather annoying function.

7:14 it drops down to essentially a this number if you have just a one followed by all zeros but then it might go up to almost twice that. So most of the time we get away with pretending theta is like this tilda asmtoic. We just don't know or don't care about the constant. Uh but sometimes there is no constant. So keep that in mind as kind of a um a thing in the background. Sometimes um you can still say a valid theta statement even though the tilda wasn't isn't even true.

7:56 The second little caveat is something that will come up in the modules. I'm I'm only trying to uh prep you there a bit well in advance. We would sometimes like to write things like this. Maybe you've even seen this. That could be the running time of say bre first search in a graph. It has a graph that has n vertices and m edges. Uh a traversal takes theta of n + m time. But what does that actually mean? Um where is my limit? I was very diligent so far with defining oh there's a function in n and then as I take the limit as n goes to infinity. But now here I suddenly have two variables. So what should I'm what should I even understand this to mean? Um there's many ways to define it which are not giving the right meaning to this theta term in several variables. Not the meaning you would want it to have. And let me skip all the corner cases in the hows and wise. Um as a as a warning sign if you look this up online or in the literature you find some inconsistent definitions. Some people do do one thing, some people do the other thing.

9:10 Uh the right way obviously is this. There's a hidden variable that actually goes to infinity. Let's say we call that n and it may be this n or it may be a third variable. That's the one that we actually consider the limit in. And all the other variables are functions of this single variable. That's the only real sense how you can define limits. A limit is always onedimensional. Even if you're talking about objects in higher dimensions, you have to relate these somehow.

9:44 And so the benefit of this few is that you can make assumptions about how these other parameters grow with n. And that means you can be explicit. For example, in a graph, we usually assume if it's connected and simple, we can we can assume something about the number of edges. If the graph is supposed to be connected, it needs n minus one edges. So at least um theta omega n. And if it's a simple graph, any two vertices are connected or at most once. And I can have at most n choose two edges. So quadratic as an upper bound. And then I can work with these constraints to compare different theta terms properly. We'll do this usually on an intuitive level in the chapter on graph algorithms. But if ever the need arises for you to double check, for example, if this is true, uh you need essentially to um somehow specify the conditions of how one parameter grows with the others.

10:48 For example, big O of N plus M is smaller than the the product of those two. Well, precisely when M is at least a constant. And you can think about of course this is wrong. If m was something absurd like 1 / 2 ^ n, something that goes to zero very very quickly, then if you multiply n * m, as a counter example. If if m were to grow very very very drop to zero very rapidly you can multiply this by n and it still drops to zero. So that means this right hand side goes to zero as n becomes bigger whereas the left hand side doesn't m goes to zero but n just grows.

11:43 So then this statement wouldn't be true and that's why I think this is the right way to go. You have a single variable that goes to infinity. So all your limits are well defined, but you have to think about how the parameters relate to each other. And that's a pro because it makes these assumptions explicit.

12:18 will function because it will change how >> yeah how do I choose these these functions or how do I choose these site conditions and this this should come from the problem specification for example these precisely correspond to the knowledge about the input. If it's a graph, if the graph is connected and simple, I know these two are true. And so I can make derivations. For example, I can say that the sum of n and m linear in the graph size is better than n * n. But I can only make this this statement that this is smaller than this in big O statements if I have this assumption that M is at least a constant otherwise it's just false right so where do these come from I mean the two answers one it could be just that they make sense in your application and uh if either of them is violated then it's not a valid input to this problem or the other the other option is you want to make a statement ment about some classes of functions and you work out what is the weakest requirement I need and for that you could again take just a take the quotient and see when it fails to be bounded or something like