Video 2-3: Asymptotics and Big-Oh

0:02 So, the next section is about asymptotics, big O notation that is uh used widely in in algorithms. And to see from where people start, uh I'd like start with a little question, so you can head over to Slido on on the link below.

0:23 And give me the correct way to uh complete this this equation. And of course, the experts will recognize this is already a bit of an abuse of notation to say that this is an equation.

0:35 We'll come back to that. 10 is roughly what we have in the room. There's a few more people online. So, maybe I'm I'll wait another 10 seconds or so. 13. Anyone's too busy thinking?

1:37 Seems not. So, also um people all are happy with this and know what the big O notation in principle works. So, here D is correct because I have this quadratic part that dominates the growth. That is, if I make n bigger and bigger, this will be much much larger than any of the other two. and it has the main growth rate of n squared.

2:04 Before we get to the definition, let me motivate again why we do this even in in algorithms. I could also design algorithms that are fast on the very small inputs, but really the challenge or where things are important to get right is when you deal with larger inputs. So, you should think of as you approach the horizon uh what we care about is um the the limit of the speed if you make inputs bigger and bigger. Designing scalable systems. And asymptotic notation can then help us by abstracting from unnecessary details that may matter in the first few steps, but in the long run if the inputs get bigger and bigger don't do well matter as much don't matter as much. Uh and maybe also just even to decide which of two alternative approaches for solving a problem is better. I might have contradicting evidence um up to a certain point one algorithm may be better and then from a certain point on another one is better.

3:04 So, I need somehow a way to decide which um which algorithm to focus on. Uh now in in such a case in practice it often is okay to do a a hybrid algorithm that switches between those two if it's such such a clear-cut example.

3:21 The way to intuitively think about asymptotics is as an approximation for a function around this point infinity. It's a bit of a strange thing to say, but uh it's a way to write a function, replace it with a simpler function like this example here. Um that's a complicated function. It may be the running time of some algorithm. And here's a plot uh if things go well, then we can replace it with a a simpler function and the change in the actual value is is rather modest.

3:58 So, it's an approximation with something simpler. An approximation around infinity just means that it's valid or it's a it's a good approximation. It's close to the true value as the parameter n becomes bigger and bigger. Okay.

4:20 Formally, um let me give you the following definition that I'm I'm always using. And there's a reason I'll come to why I think this is the most convenient way to define it. The strictest version of approximation is this asymptotic equivalence. So, we write that with a with a tilde. Um this does not um throw away constants. So, when you when we when you can prove such an approximation, you know the value much more precisely. And it's the easiest to define. You just take the ratio of the two functions and uh request that they that the ratio converges to one. So, as you get bigger and bigger, the relative error you make gets smaller and smaller.

5:06 Then we call these two asymptotically equivalent. That's kind of the gold standard to aim for. Sometimes this is too much to ask for. And then there's the slightly weaker um approximations. In particular, the big O notation that you will know or that you've seen in the example. Uh there we also take the ratio. It's the same ratio, the function on the left side divided by the function on the right-hand side. But now I don't require this to be converging to one. I'm okay as long as it converges to something less than infinity. It should just not diverge away to infinity. Uh to be a bit more careful, we want the absolute value to be bounded. So, I'm happy if either of these functions is negative. We'll just ignore the sign. Uh we shouldn't have g of n zero all that often. A finite number of times maybe you can say it's okay, but then from some n onwards it shouldn't be zero anymore.

6:05 Then I can divide by it. And a formal way to write this stays bounded is limit superior. Um we'll not usually need that distinction, but that's the formal way to define it. And there's two variants that are also in common use in algorithms. Big omega is um a lower bound. So, here I guess let me show the intuitive version first. If f is big O of g of n, what you should think of is f is smaller than g. But it's a bit of a lie. There's two caveats you have to add to. First, only up to constant factors. I may have to scale g up by a certain constant. And second, it may be violated for very small inputs, but from some threshold n zero onwards, this function f is always below a scaled up version of g. So, big O is a a bit like an upper bound or a less or equal.

7:10 Right? But treat that with a lot of caution because um it's not the usual less or equal. It has a bit more of a refined meaning. If f is big O of g of n is less or equal, then the omega is greater equal. And formally we just flip it around. f is in omega of g if g is in big O of f. If you think about how less or equal and greater equal work, this is what you would want to define. And then big theta is that the F is in both it's both upper bounded by G and lower bounded by G. Which should mean in normal ordering relations, they're the same. Uh for the slightly uh weaker version of of O and omega, it doesn't mean the same. It's just roughly the same but up to constant factors. And again, same two caveats if you're if you look at it more precisely.

8:08 If F is big theta of G you should think of F being sandwiched between two copies of of G scaled with different constants. A smaller constant gives you a bound that F doesn't go below and a larger constant gives you an upper bound that F doesn't go above. And all of this is true only from some starting value onwards. Okay? All of these make make algorithmic sense. You often have some special treatment for small cases where things may be a bit more wonky. And uh scaling up by a certain constant, people usually justify by saying I don't know what machine I'll run on and so the best I I'm able to say is about the order of growth and not specifically about 50 seconds or whatever it is that depends on the machine.

9:01 Okay. Uh let me also mention the little variants. If big O is less or equal than the little O should be a strictly less. Formally speaking, it's the uh ratio goes to zero. So as as N goes to infinity this F is much much smaller than G.

9:26 It is what what that statement says. It's asymptotically strictly small slower growing. And formally you always take the ratio. Now what what you may notice that for all of these definitions, no matter which outcome you're looking at, you always take the ratio f divided by g, and look what happens if you take the limit. And for well-behaved usual functions, as they might come up in a written exam in some class, for example, you usually get by if just computing that limit. And only occasionally, if somebody has a a bad day, then the function doesn't properly converge, and you have to check if at least the ratio stays bounded. Um we'll see some examples, uh also the tutorials for that. Okay. Um questions up to this point?

10:35 uh the intuitive version that's on the slide is really what you should um focus on. But I want to motivate briefly why I torture you with the formal definitions, just in case. So, usually you get by if you plot the functions for large n, then the one that grows asymptotically faster should also be higher, should be a bigger value, right? That's the whole point about asymptotic notation, that if you make as you make n bigger and bigger, that one function is just way bigger than the other. Now, if you put your mathematics head on, sometimes you have to be a bit more careful. Here's two functions that are um for now, say unknown. And I'm plotting these from zero up to 500, and I don't know if you can read the numbers, maybe a bit small. They don't really get larger. And it looks like F, the red function, grows much faster. Okay. Now, if you zoom out a bit and um look at up to 2,000, something strange happens. This F is somehow overtaken by G.

11:50 Well, it can happen, right? Mhm. Maybe it's just a the turnover point was a bit lower uh with a bit bigger. If you go up to 10,000, indeed it looks like now G is actually faster, right? And um F after all was faster. It only was higher only on the small values. If you go to 200,000, oops, here G was the upper one. Now it's F again. And if you go to 10 million, it's G again. So, what's going on here? So, my point is these are real functions. I'll show you what the functions are in a second, and there it is not no cheating involved. The plots are real and all that. The the point is just for uh adversarially chosen functions, which these are, you cannot really look at a plot, and even though it looks smooth and the one function clearly is larger and keeps accelerating than the other, uh the answer in this case is different.

12:46 Uh first of all, if you slowly scroll up and down, you see what happens a bit. The two functions wiggle around each other. And it gets even um clearer if you take a log-log plot, then you really see now with logarithmic axes on both, you see that they're slowly uh well, blue is dancing around red, you could say. And if you look at the ratio between the two, so that's uh let me switch back, but this this here is just um I guess G F divided G. And then you see this is between whatever that is, uh point 37.63.

13:30 So, it's periodic. It's clearly some sign function, and it's bounded between two numbers, very tame, between uh say a third and and uh 5/3.

13:44 So, in terms of uh if you look at the ratio, that ratio stays bounded. It's bounded from below and from above by a constant that is not zero. So, the two functions are in big theta of each other. But, looking at these plots again, you may not have guessed. Um Do I not have the Okay. Uh this I need to add. I don't I don't have the the terms defining the functions on the plot. But, it's essentially taking um is a quadratic function where you have uh a sign, and then you integrate. So, it's a linear function with a sign offset, and then you integrate twice. That's how this this um wobbly function is generated. Um Uh you can also go to the old school uh link if you if you open the slides.

14:58 So, with that caveat, um if you need to be sure, if you want to have a formal proof, you take the quotient of the two functions and uh take the limit.

15:16 Let's maybe do one example together of how you formally prove asymptotics. So, we've seen some some basic examples and in the first question, but let me um for the sake of the argument prove one of these here. Suppose we want to prove that this function here f of n is big O of g of n. g of n this function, so n n cubed.

15:50 What I have to do to show such a statement is as always take the quotient. So, I'm looking at f of n divided by g of n which in this case is this lovely term. Um Trying to not write this too many more times, but at least once let's do it. plus five divided by n cubed.

16:18 Now, in in this case I can split this up into several uh fractions. So, it's 20 plus then plus this. At this point, you may see that this will stay bounded because uh all of these converge to zero.

17:04 in this case it's even easy to compute the precise limit. It'll just be this constant 20. And because 20 is less than infinity and I have a proper limit uh I can conclude that indeed f is in big O of G of N. And I even proved this first statement which is a bit more precise. Because if I take as G 20 N cubed, then of course I get instead of the 20 a limit one for the quotient. And so I've I've proven this part almost with the same calculation. For the big theta I would have to prove the other direction as well. So I would have to take the reciprocal of the quotient and show that that is also bounded. And it has the same limit as a limit the reciprocal, so it's bounded by 1 over 20 in the limit. Also less than infinity. So I get the big theta statement out of that.

18:06 You'll do a bunch of more examples in the tutorials and then I've asked the tutors to be really diligent and um give you feedback on whether that's formal enough. We'll be a bit more strict in the tutorials at this point in time than we will be in the exam. The point is that you should once practice how to do it very rigorously and then afterwards be pardoned if you take shortcuts. But at at that level of formality we want to see things.

18:48 Let's do one more check. If we're on the same page. >> Okay, I want to see at least the 14 votes from earlier. 12 13 Amazing. Thanks.

20:04 There's a certain majority, but there's a bit of a discussion point here. Um the majority is right in this case, though. Let's see why. And again, resist the temptation to change your answer now. It's uh just for uh your own um entertainment here. Why is that the same Why is that uh a true statement? Well, if if it's a bit hard to intuit to give an intuitive reasoning, let's not and uh just do the limit.

20:37 this lovely function, and you divide by G, N squared, and you look what happens if N goes to infinity. I guess I formally should have put um absolute values around these, but these are all positive functions, so it doesn't make a difference. As you'll see, the N squared cancels. So, we're left with the question, what is uh the limit of sign? That's a problem, right? So, at this point, it helps that the function that the definition is a bit more lenient here. Because what does this sine of n plus two look like? Sine of course is this up and down and the plus two moves it enough above zero that we don't get close enough to it. This this function will be between one and three at all times. In particular, this is always less than three. Which is very bounded. And so the limit superior, who knows what that is in detail, but it's at most three here because I cannot have even any value above three for this function.

21:49 So it's bounded, hence this function is in big O of n squared. But you can also take the reciprocals, then you ask the question about one over sine of n plus two. That is still a function between one and three, so take the reciprocal. Let's do it maybe once. So you take n squared divided sine n plus two n squared. Of course the same cancellation happens, so you have one over.

22:27 And now this function is always um at most one, I guess. And that's also very bounded. So also our function is big omega of n squared and the two together means it's big theta. Okay? No need to doubt yourself. Um you just uh plug in and compute the limit. Uh by the way, let me say at this point this is something if you're if you're struggling on some some question, you can easily double check yourself. Um of course asking an is one option, but better than that is even Wolfram Alpha, where you can compute limits and you have a bit more certainty that the answer is actually correct than some random gen AI.

23:17 That won't help you in an exam, but um, or practicing, it is very useful. And for exercise problems, it's halfway accepted to double-check yourself. You will still have to justify why it's correct. Okay, so that's that's that. You can sometimes have these um, non-converging limits, not a problem for the big O definitions. Uh, there's a few rules on how you can work with these big O notations, which you'll practice much more in the tutorials and many of you will know. So, F is always in theta of itself. If F is in theta of G and G is in theta of H, then the uh, translate the the property is is transitive. F is also in theta of G of H. Constants are absorbed by theta. You can rewrite this asymptotic equivalence in this funny form. I guess here one point is worth making. Formally speaking, what is theta of F? What does that even mean?

24:18 If I write something like this. I'm using this here in a sense of an equality, and that's of course not a sensible equality. F is the same as this weird theta thing. So, in in formal in formal language, uh-huh.

24:50 In proper set-theoretic definitions, what this um, theta of F is it's a set of functions so that this function is That's a bit Let me write it with uh the same letters we had. And then the definition of Yeah, I'll I'll define it with O, okay? lim sup of f of n divided g of n less than infinity. That was the definition. And you can insert this definition for theta or omega. All of these are defined the same way. My point here is it is a set of functions. So, if that is a set of functions and this is a single function, it doesn't make sense to declare that these are equal. What I should really have written in all of these places to be strict is an element. f of g uh O of g It should always be an element sign. And then in other cases like here, I'm making a statement about uh different sets of functions.

26:05 Uh here it might even work. Um And this really should mean subset. These equations are a bit funny in that they're they're directional equations. They're left to right equations. They work from the left to the right, and if you swap the two sides, they're no longer the same. I think this is essentially historic. When people started writing about algorithms, this was done on typewriters, and the poor people didn't have proper math symbols. And so, out of laziness out of convenience, they used the equality sign, which was available on typewriters. And in a way, it's a horrible abuse of notation. But it's so much ingrained in the culture that people decided to stick with it. Also, it speaks a bit more fluently to say F is O of F of N. You could even is in as an English word, you could say it means element or subset in with a certain reading of the sentence.

27:17 So, maybe it's less of a lie if you if you read it out. But be careful that in principle, you should use these set theoretic notations in if in doubt, and things like this. Even for theta would be Uh no, it's not true then.

27:45 Okay, so um that brings me to the question, what does even stuff like this mean? If I have uh a term, a function, and then I'm multiplying that with something else.

27:59 And that involves some O term. This this big little O of one of course is all the functions, so that if I divide them by one, they converge to zero, which means all the functions that vanish. But what does that mean? I cannot add a function to the number a set of functions to the number one. So, again here, what this means is it's another set of functions. It's the set of functions H so that I can write H of N equal to something like this. And this plus minus is my um my abbreviation for that the function is is in between these two. So, let me maybe also rewrite this part. Um Let's first define it for plus.

29:05 Uh another function. I'm running out of letters. Let's say K of N. And then this K of N should be in the set of functions little low of one. In general, if somebody writes such a an expression involving big O terms, it means you are talking about a set of functions that can be written in such a form. So that you replace this by some concrete function, and that function has to be from the set. And then the plus minus on top of that adds that this could either be plus or minus.

30:11 And now it gets close to a bit unreadable, so you see why people use these abbreviations. Okay, if you take um two theta classes and you multiply them, that's the same as doing the multiplication on the functions. That's essentially unfolding this definition. A bit more interesting is if you take the maximum of two functions, that's the same as taking the the sum. Yeah.

30:45 Sure. So a little bit of time rule is for computing limits. And it's often the way to make progress if you want to formally prove that certain limits are the way they are. And then of course you can use this for your for your proofs you can always use true facts from analysis. And so that's one of them. My my whole point with these definitions also is all we're doing with asymptotics is analysis. It's real analysis and this is kind of something you know. Another question?

31:36 The little o that is the set of all functions where this converges to zero. It's this one. No, cuz limit is zero. Yeah, yeah. So here again little o of one is the set of all functions so that one divided by the function converges to zero.

32:20 Uh sorry, the other way around. F divided one converges to zero. And that's of course the same as the function converges to zero. Well, I'm I'm asking here if some You should think of the question is F element is set little of one.

33:04 Little of one should be the set of functions for which this is true. Well, let me stick with the equality here, even though it's a bit of a lie. It's a set of functions for which this is true, which means it's a set set of functions F where F divided the thing in the brackets converges blah blah blah. Yeah.

33:38 It depends on the left-hand side whether it's an element or a subset. If the left-hand side is a concrete function, it has to be element. Doesn't make sense that the a function a specific thing is a subset of something else if that's not a set. But if it's another theta term which is a set of functions, then it has to mean subset.

34:01 Yeah, you you'll have to get acquainted with this kind of sloppy notation. It's too widespread to change now, I think. Yeah. I think if you plug in what I said is the meaning of such a a a combined term, >> [sighs] >> uh this one is almost by definition true. This one has uh the second part is a bit non-trivial because you're replacing the sum by the maximum. That needn't be true, but it turns out it is. Right?

34:54 You can just bounce the sum uh and the maximum you can bound in terms of each other. The maximum is never more than the sum. And the sum is never more than two times the maximum. So, they're within a constant factor of each other. More questions?

35:16 Uh, element-wise maximum. Right? So, you Uh, the function max FG I should probably write it like this. So, FG and then this whole thing is a function. So, I could uh ask what its value at a certain value n is. And then of course, you know what to do, right? Uh, it's the maximum of f of n and g of n.

35:47 And that we know what it is. Okay. Um Enough confusion from the big O notation for the moment. Uh, as I said, you'll you'll practice this more in the tutorials. I think it all looks scarier than it really is. Compute limits and almost all of the cases that we care about will be fine. Um, the usual things that we you encounter in algorithms as growth rates are these typical functions. So, maybe a constant, it doesn't grow at all, or logarithmic, or linear, then this portmanteau of linear and a log, so linear rhythmic, uh quadratic and cubic. Um sometimes we speak of just polynomial if the the power isn't fixed, but it needs to be some constant. An exponential means there's a constant uh as the basis, but n is in the exponent. Um I think these when they when they pop up, you will see these are the the typical terms that we then associate with algorithms.

36:52 Of course, in practice, really the line goes somewhere between these. Anything above is scalable. If you make n bigger, then this doesn't grow by much. Whereas anything below the line usually is a problem in practice. At least if the inputs get big.