Video 1-3: §1.3 Asymptotics and Big-Oh

0:00 Intro

0:03 And the last subsection of our unit one on on machines and models uh and abstractions, we'll we'll talk about asymptotics. That's the key mathematical abstraction that we'll use in the analysis of algorithms. It just turns out to be a very convenient language uh to talk about I suppose that many of you will have seen big O already a bit. Uh again, I'll I'll try to do both, very quickly introduce the basics, but also give you a maybe a a more formal definition than some of you have seen or a slightly different definition than some of you have seen. Uh if if you feel like you want to discuss why I put that definition, uh find me offline. I'm uh happy to chat about that, but it's not relevant for the module.

0:47 Clicker Question

0:50 So, let's test um if you've done this before. Have to find my poll. So, that's a question that tests what you've done before, right? So, that tells me how how much detail I have to uh give for the rest of this subsection. If you've never seen this, if you want to put E, put E.

2:05 I think we had a few more people vote before, but then yeah, some some were just arriving. Hm. Okay. Yeah. It's this room again. Uh I'm having a lag with uh synchronization on the phone. Well, so uh let me also show the correct answer, but resist the urge to change yours. Show correct answer, please. Okay.

2:50 Uh we'll we'll talk about this more, but there's a dominant term n squared, and that means the whole thing is in O of n squared. I don't want to comment on this much further. So, many of you seems seem to have seen it, but a few have never seen it really, so uh it's basically for you as well to see why I'm doing this introduction for undergrads and at the same time uh running quite fast through it.

3:20 Why asymptotics?

3:24 Let me motivate a bit why we do all this before I really tell you what asymptotics is. Uh we talked about the machine model last time and already had some discussions. Does it really make sense that this RAM model has a word size that grows with the input and all this unbounded resources is all a bit awkward. The thing is, if you want a solid theory, you have to live with ever-growing inputs. Uh if you can't make a statement about uh the limit of of infinitely big inputs, the whole theory becomes uninteresting in a way. There's always an algorithm for finite cases that's better by just special casing all those finite cases. Make one big lookup table, and all all possible solutions can be in there. Unless you have a sensible way to exclude such uninteresting algorithms, the theory is kind of breaking down. Uh from the practical side, it turned out that most of these algorithms that are good in theory are also very useful in practice. There are some some funny exceptions to this rule, uh but by and large, for most of the results, uh if the algorithm works well in theory, it turned out to be useful in practice.

4:35 And so, uh this was fruitful. So, we have to live with the fact that inputs get larger and larger. Now, uh it can be very clumsy to work with this, so we use asymptotics to abstract from unnecessary detail, and we'll see what what is unnecessary in a second. Uh it simplifies the analysis, so just the the mechanical act of saying how good is this algorithm, answering that question in in the language we want, becomes easier if you use asymptotics. And if you want to compare two algorithms, uh it becomes almost necessary to do something like that. So, if I was to ask you uh what's faster, walking or taking the train?

5:25 You should probably ask, depends. I mean, where do you want to go to? From here to the Ashton Building? Uh the train probably sucks. If you add to the equation that you first have to build a track, maybe build a train in the first place, uh it takes ages, but of course, if I wanted to walk from here to, I don't know, the south of Italy or or take the Trans-Siberian Railway to make an extreme case, even if I was to walk while they start building, they might they might get there first because they build in parallel. So, it it really depends. What we're interested in mostly is the big inputs, the horizon, the long distances in that uh metaphor.

6:08 So, if you want to think about asymptotics, it's an it's an approximation of a function around infinity. What does the function look like around infinity? Now, most functions will have a value of infinite of infinity at if the parameter is infinity is infinite, then also the value of the function is infinite, but the we can still have a meaningful way of approximating how the function approaches infinity. Uh as an example, uh this is one I made up. I don't know if there's a an algorithm that really has this cost, but there could be. Uh And so, this is a a fairly complicated term. It looks ugly. It has all sorts of weird functions, logarithms, uh rounding down, so these floor uh brackets mean rounding to the the nearest smaller integer. Um it all looks pretty messy. If you plotted, it has some fairly smooth shape, but these jumps at powers of two and all that mess.

7:06 Uh whereas we can give an asymptotic approximation, which is much shorter as a mathematical term, and comes quite close in the in the abs in the actual value. And so, we'll usually focus on just looking at these, comparing these. That's what asymptotics is about. Note that asymptotics is not the same as big O terms. I repeat, asymptotics is not identical to big O terms. In particular, giving up constant factors for those who have seen this before is not necessary in asymptotics. You can keep the constant factors and still make precise uh statements.

7:51 So, the first and most precise or most useful notion of of an asymptotic approximation is this tilde notation. We can say two functions are asymptotically equivalent.

8:02 And what that means is that if you take the ratio of those two functions, that ratio approaches one. That's the strongest notion of asymptotic approximation that we have. It's the most precise notion. If you can prove some some approximation like this, it's usually the best way to express the cost. And that's what we had in the last slide, right? This is the tilde notation.

8:25 Asymptotic tools - Formal & definitive definition

8:28 Now, uh sometimes this is inconvenient or sometimes it's hard to show. Uh we'll come back to that. And so, there other asymptotic notions that are more widely used. Um partly for good reasons, partly for laziness. And that's big O notation. So, you can you can say uh this function is O of G of n, f of n is O of G of n. And that has a certain meaning. Uh I want to comment on this first. Formally speaking, big O of G of n is not a single function. So, in in this case here, these were two concrete functions, and you could say they're equivalent in a certain way, so they're asymptotically equivalent. That had a a reasonable meaning. For big O, uh big O of G of n is a whole set of functions. So, formally appropriate would be to say f is an element of this set of But, I guess because people started typing asymptotic statements before they had uh on typewriters, where they didn't have the element symbol, that's my most likely explanation, they just use an equality sign here.

9:37 But, it really is a one-way inequality a one-way equality. It's a bit inconvenient. Uh but, you'll have to deal with it because everyone's using it that way. So, I'll just write equal or element uh interchangeably in this context. Um but, the meaning always should be element. F is an element of this set of functions O of G.

10:03 Now, what does this statement mean? I try to relate this to the uh upper definition. We again take quotients. So, whenever you talk about asymptotics, you always take the the ratio of one function divided by the other and look at what happens with that quotient as the parameter becomes large. Uh one notion is it has to go to one, the other notion here is it has to be bounded in terms of absolute value.

10:31 Okay? Now, uh a slight twist on this is we don't insist So, uh a limit statement doesn't need this, but it could be that G of N is zero a couple of times. And then uh all mathematicians freak out, you can't divide by zero, I don't know, tear your hair out. That's why we say it's fine to just have this boundedness from some value onwards, for any N bigger than some threshold N0.

11:03 Uh another fancy way of saying the same thing is that the the limit the this limit superior is bounded. I don't know, if you feel more comfortable using that, that's fine. It's the same thing. These two variants that will also use, um I'll comment on the intuitive meaning of these in a second. Uh we'll say F is big omega of G if G is big O of F, so it's flipped. Uh and then theta is combining the two statements. F is in theta of G of N if it's both in O of G and in omega of G.

11:41 Uh and there's uh another notion, I'll come to that in a second, but I first want to give this picture. So, if you haven't seen this, I should have really started with it with that picture, but for the majority of people this was maybe useful to first see the definition, so you can think about it and tune out for now. Uh what does what does that statement intuitively mean that F is O of G? It's basically saying F is smaller than G, but with a few caveats. The first is we ignore constant factors. So, it could be that if uh our function F is this this fat red line, we have to multiply the function G by some constant C before F is properly below C times G of N. And the second caveat, only for sufficiently large N do we require this. So, there's some threshold N0, before that we don't really care what happens, but after that F has to stay properly below C times G of N.

11:44 Asymptotic tools - Intuition

12:40 All right? So, uh you can think of this big O is always something like smaller. But, uh with these two uh what qualifiers. Uh and similarly, the theta notion, which is the other one that we'll use most frequently, F is theta of G if it can be sandwiched between uh a small constant times G and a big constant times G. Again, uh starting from some value. So, what this means is that the two are really equal in a certain fuzzy sense. They're equal up to constant factors and only for sufficiently large N. Question?

13:29 Yeah, so for those who arrive late, you can look at the attendance code on the live stream later. There must be a little bit of punishment for not being on time.

14:08 Yep. So, you're saying uh big O is an upper bound and uh big omega is a lower bound uh for the function. I I mean, that's what the the plot's getting at with the less or equal sign. Uh is another useful term. So, you can you can say this is an upper bound for F.

14:28 Uh for theta, I don't really have a great it's an approximation for for G. I want to briefly come back to the little cousins of big O. If they're called big O and big omega, etc., there must be also little O. And there is. So, that's um similar to big O, little O is an upper bound, a less or equal, but it's a strict less. So, it's uh if if big O is something like less or equal, then small O is strictly less. But, in a very very strict sense, uh so this is not the same as saying that F is always strictly less than G. It's much stronger. It's saying that if you take the ratio, it goes to zero. Okay? Not just some constant less than one. And we have little omega, which is the opposite. Uh then the the ratio goes to infinity, which means F is strictly bigger than G in that sense.

15:42 Sorry, not sure I understand the question. Uh I see. Okay, it's a subset. Yeah, so little O of G is a subset of big O of G. That should be should be true. Yep.

16:09 I think it's fair to say you can usually just memorize these pictures. But, I want to throw in a caveat that uh just plotting a function and trying to derive from that is this an upper bound asymptotically or not uh can be misleading or dangerous or something along the way. I want to show you a little example of that just to make make that point really clear. Um so, here's here's a plot of two functions, right? Uh a green and a red one. I don't know which one is what. Uh so, from this first plot it it really looks like, okay, green is bigger first, but then red takes over. And it takes over and becomes steeper, right? So, clearly it's asymptotically faster growing. Uh that's what this plot looks like, and if you go further out, if you plot the function, okay, giving away the the surprise. If you zoom out a bit more, make the plot for larger inputs, yeah, clearly uh like uh confirmed, right? Red goes even bigger and even bigger.

17:16 Only that if you go much further out, then suddenly the picture flips. And so, okay, you could say, okay, I cheated. I just created these these manually these pictures, right? There's no real functions behind this. Uh but there are two functions. These are the functions, I mean, they're contrived examples. I made them up so that the plots look really weird and misleading. And it turns out the two functions are asymptotically equivalent. So, if you take the ratio and divide, so this goes to one. There's really no no asymptotic difference between the two. Uh but because they're created in a in a very uh naughty way, uh they look like in a fixed fixed prefix of the integers, they look like one is much faster growing than the other. So, just be uh a little careful. While these pictures are useful and for well-behaved functions, where I can't really say uh how you recognize one, uh it can be enough to plot them and then get a get a guess.

18:21 But, the only proper way is to go through the definition, take the limits and compute uh take the ratio and compute limits. All right, let's uh wake you up a bit.

18:39 Not much comments, so this is about asking relations between the two things. How many answers did we have in the last questions? It's always fun to see the results and you cannot yet.

20:14 I've seen the 75. And maybe we can get at least 70 before I reveal anything. 3 2 1 I'm at least showing the results. All right. So there was no no trick question. Uh almost no. If if f is o of g of n, that means f is essentially smaller than g. And so if you flip that around, g should be bigger than f. That's the the vague intuition. And in in yeah, in in principle, this is uh happens here.

21:12 Now there's um a slight If you want to be nasty, you could say if one of the functions is zero, then the definition don't really work. The definitions don't work so well and it's not really clear what we mean and blah blah blah. Uh we'll often not deal with functions that are zero because these are usually resources running times.

21:44 Uh are you asking about the element sign and the equal sign? Yep. Yeah. So if if f can be zero, if if say say f is all zero, uh constant zero, then this would still be a true statement. Zero is smaller than g of n even if you throw in the uh extra conditions up to constant factors starting from some uh threshold value n zero. But uh nothing is omega of zero uh Yeah, not nothing's really um omega of zero just because we had to divide by zero to as kind of a uh just a gap in the definition, if you like. So in that sense, it depends depends on on f and g. But that's really the only thing.

22:37 We're right above the trains in case you wonder what the sound might be. Uh I'm not sure. It sounded like more it comes from above.

22:52 Let's do a few examples. Uh I'll be fairly quick. So for this first one, we always just take the function that we want to test. And copying it takes the most time.

23:08 Uh and we divide it by the function we want to test it against. And now we have to compute the limit of that. Now this in this case uh is relatively convenient to just um pull out this as a factor. So uh in slow mode, we could say that's that plus whatever that is divided 20 n cubed uh plus five divided 20 n cubed. And then we divide by 20 n cubed. So this goes away. Uh if you look at the remaining terms here, this one converges to zero and this one converges to zero uh because it's effectively n n cubed grows faster. If you wanted to to properly prove this, you would use L'Hôpital's rule because it's a a quotient of infinity divide infinity. So you take derivatives. If you do this often enough, there's a constant remaining on the top and some non-constant factor at the bottom, so that goes to zero. Okay?

24:26 Uh if you don't remember that stuff, that's really high school math. There's lovely YouTube videos re- refreshing on that. So what what that means um is that this this limit should have said uh the limit equals the limit.

24:53 Now having a limit of one means the two functions are asymptotically equivalent. And it turns out that you can do uh the same calculation without really changing much. If I just remove the 20 here, then what I'm left with, I would still have the 20 here. So this is also gone. And so I would have one over 20. If I take just the function and divide it by n cubed, okay? So if I take the function divide by that g of n here, I get a a limiting ratio of one over 20, which famously is less than infinity. It's a constant. That proves that so the fact that this is less than infinity proves that our function here uh I should really give this a name.

25:57 That proves that f of n is big o of n cubed. Okay? If you just go back to the definition, ratio limited in absolute value means a bound in absolute value means big o. We can flip the whole thing around. Uh if we want to test for omega, we would have to divide n cubed divided by f. You do the same calculation, you get it to the same results except that now the uh result is 20. So if you take n cubed divided f of n, the limit of that would be 20, which also is less than infinity. So that would say n cubed is o of f of n. And uh we've just seen this is essentially the same because the functions are not zero of saying that f is omega of n cubed. And if you have big o and big omega together, you get big theta. Okay? So that was this this first one.

26:57 For the other ones, uh I'll go a bit faster. So for this one, again, we take the function. What's this? log of log of n. Uh in case you wonder, so I'll I'll usually write ln as an aside. Uh ln is the natural log of e, so base e, Euler's number, 2.7 whatever. And we write lg for the binary logarithm.

27:39 It's convenient to have uh an extra name for that because we'll use binary logarithm so much so much. So for the second example, we take our function, we divide by log. Now if I just write log without any base, that should be a mistake except if it is inside a theta term because there the base, as long as it's constant, doesn't matter. But you can say as a default, we take uh log base two.

27:41 Asymptotics - Example 1

28:15 Now uh know that this is just a factor two that goes out and then you have log n and you have log log n. And you divide by log n. Uh these two grow roughly the same way, so the limit will be six, whereas this divided by log goes to zero. Again, if you want to prove, take L'Hôpital's rule, take the derivative of the numerator denominator. Uh here the derivative's one over n. It's more convenient to use ln. Uh here the derivative, uh you have this inner one, so there's a log, and so uh that one that that goes to zero.

29:03 So that proves the big o part. You flip it around, you get one over six instead of six. So in a way, you can shortcut a proof for big theta. If you take the quotient and it goes to a constant that's neither zero nor infinite, uh a proper number, then uh you've you've proven a big theta statement.

29:27 And the last one is really just um pointing out a slightly silly no- uh silly property of of big o. It ignores any constant factors, no matter how big they are. This 10 to uh 10 to the hundreds, uh I think it's well beyond the number of whatever particles in the universe. Uh pick pick your favorite. I mean, atoms clearly, protons maybe still. I think 10 to the 80 something is it's an estimate. Well, however accurate these estimates are, if if you ignore constants of that magnitude, you're probably on dangerous territory. Uh but the mathematics doesn't care. If you tie If you divide this constant by one, it's still not infinite. So, uh big O of one. All right. Uh because we're not a calculus class, I don't care if you use other tools to compute limits. And there's a thing called computer algebra, which is really good at computing derivatives and limits. And so, for all these functions, if you open Wolfram Alpha, type in the limit, it will instantly spit out the answer.

30:33 There's no no value gained from not telling you this. Of course, in an exam, you don't have access to that. Uh but for the class tests, I guess I don't stop you from from using Uh so, again, it's it's a skill to compute limits. But what I'm teaching you here is thinking in terms of these big O bounds and computing the limits of your favorite functions from high school. I don't really care about if you can do this on a piece of paper or if you just memorize the functions that are occurring more often and use Wolfram Alpha to check if you're not not sure. All right. Uh that's Yeah. Um that's teaching analysis assuming computers exist.

31:21 All right. Let's have another quick quick check of this. Uh don't try to go to Wolfram Alpha for this one. Uh that's not the point I'm getting at. Come on.

32:47 Okay, I'll start revealing at 60. Instead of waiting for the slowest, let's incentivize you to be faster. I'm just a naturally impatient person. You're not starting to play games with me now and all right. Okay, 60. Um It's a good good deal of um confidence in both answers. Uh it is true in this case, but let's briefly unwrap why.

33:19 Uh so, if we're doing the same thing as before, we take the functions and take the quotient. So, we have sin of n + 2 * n squared. And well, we're checking against n squared, so that's nice. Just goes away. Now, we should Well, we're supposed to compute the limit of that. Uh that's a little bit of a problem because sin is is this oscillating function somewhere between -1 and 1 all the time and keeps changing. So, it doesn't really have a nice limit. Shoot, what do we do now? Now, that's where the the more tricky part of the definition comes in. It's enough for the quotient to be bounded. Right? And so, we know that this this thing with or without the limit is always at most three. Uh because um sin is at is at most one. It's also at least one because it's sin is at least minus one. And so, those two things together are all we really need for our asymptotic statement.

34:24 So, it's not it's not really necessary that this limit has a nice that this limit exists in in the strict sense. Uh asymptotic notation ignores constant factors, and that includes the case where there is no constant constant factor. Uh bounded is enough.

34:43 Asymptotics - Frequently used facts

34:48 Uh a few facts without justification what you can do with uh these big O terms. Uh I claim that the analysis becomes simpler. So, you have to learn to man um manipulate these these uh uh big O terms. So, if we have a constant in front of some function, we can just drop that. That's by definition. Well, unless that constant is zero. Well, Um more interesting, if if you have two functions and you add those up, two different parts of the algorithm both contributing to time, that's the same as taking the maximum of the two. So, it's a little takes a little thought, but uh it's just either they're both contributing dominantly, then it's a constant factor difference, or one dominates and then the other asymptotically is irrelevant.

35:36 Uh and there's a few uh theta terms that will run into often just because there's famous algorithms that have that running time. Uh logarithmic we'll see well, theta of log n. And here what I alluded to before, as long as you have two constants A and B, the difference between log base A of n and log base B of n is just another constant and it's a non-zero constant, so you can um you get the same theta class. Uh linear, that's whenever you just read the input. n log n we'll find again uh and we sometimes call this linear linear rhythmic or linear and logarithmic for it mental. I don't know. Um Uh there was a time when I found that term really sleek. Quadratic um sometimes occurs cubic and and cubed. Uh and then we won't touch on these much in this module, but you will hear about more of this in other in other modules if you talk about efficient in the theoretical computer science sense usually means bounded by a polynomial of the input size, so n to a constant for some constant.

36:46 Uh as opposed to exponential where you have a constant and then the exponent depends on n. Uh be careful if you have exponential growth, the base does matter a lot. Uh 3 to the n is much more than 2 to the n even in the theta sense. There's not just a constant factor difference.

37:11 Any questions on this? It's probably recap for many of you, but um in case In case you've never seen this, just like a bookmark the page in if that's that's a feature for you.

37:23 Asymptotics - Example 2

37:26 I want to finish off that subsection with a little more real example, which also shows why we need these slightly more complicated definitions sometimes. Uh the code on the right is is real Python code. Um I didn't know about this built-in function of Python, but it's a built-in function of Python, bin, binary, that takes a number and uh returns essentially the binary representation, so the the bits of the binary representation. Of course, there's other ways to compute this, but um yeah, and interestingly, it has some extra stuff at the beginning. So, if you just want the bits, you have to start with the position two. Uh don't ask me why. I mean, um but that's that's a way in Python to compute the binary representation of a number. What this function does is it takes a real number x and raises it to an integer power m. Now, of course, there's many ways to do this. Uh for example, the stupid way would be to just have a result variable, start with x, and then m times multiply x into this.

38:34 It turns out there's a faster way, and this method is um is that algorithm where you repeatedly square and multiply. That's why it's called the square multiply algorithm. Sometimes names are easy. Uh again, it doesn't matter all that much why and how this method works. You can You can Google it if you're interested. Uh let's just take the code as it is. Um maybe let's see if there's uh unintuitive bits. So, this is a list of the bits of the exponent. Um that's just the result is just a variable, and then for each bit in the exponent bits, um now, this starts with the most significant digit in case it matters. So, the the natural way, right? You write the numbers numbers left to right, and so you would iterate left to right through the bits. Um yeah, and this this operator, I mean, that's the it takes result, multiplies it by result, and assigns the value the result to result. Uh should have called that variable differently.

39:42 You've all seen these kind of operators. It's a shorthand for result equals result times result. Uh not that you could read this, but three times result. Good.

40:02 What is the cost of this algorithm of this Python code? We have a few parameters. We have M, which is um uh which is given as uh well, that's that's the value of the exponent really. Uh and we have N, which is the number of bits in this number. That's the length of this list exponent bits. Uh and the other input is X, which is just some floating-point number. Um we don't care about this too much. What we assume here, that's why it says floating-point number, is that it fits in one word. Okay? So, an extension of our RAM model would have logic for doing floating-point arithmetic instead of just integers. You can imagine that you can build this from trickery with bits, bitwise ands and ors and these things. So, we'll usually assume that this uh this is already given and it takes constant time. So, these these kind of multiplications are assumed to take constant time because they work on floating-point numbers.

41:03 To make our life easy, we'll just say the cost of the function is the number of multiplications. Then uh we're sweeping any complications under the rug if that multiplication is more expensive or not. So, how many multiplications do we have in this piece of code? We always do one in line four. Well, that's uh just an assignment, but did I change the code there maybe?

41:32 I think the line numbers are not correct. This was for the Java version. Apologies, yeah. We always do this one, no matter what uh the bit it is like, but then line eight, uh that one we only execute for one bit.

41:53 So, what we can uh derive from this is the number of multiplications is between N and 2N. But, what does that mean in terms of asymptotics? Uh that's the question for you.

42:30 Uh for this answer, you can you can type in free text, so you can send uh whatever you think is the the best approximation.

42:38 Uh you can just say something like this. Theta of square root of N or whatever you think, and I'll go back to the slide so you can uh keep looking at that one.

43:42 Okay, we still have relatively few votes, but maybe in the interest of time Let me let me start showing the results. It makes these nice little word clouds, and there are some guesses.

44:40 uh the answer is is well, the most voted answer is correct, theta of N. Uh which you can express as theta of log of M. I just wrote this to finish off the the application in a way. Uh if if you look, M M is the exponent as a number. If you had just repeated M times multiply X with itself, that would have been theta of M multiplications. Whereas, it looks like we get that down to theta of log M. That's an exponential improvement, right? Okay. Uh so, why is it theta M uh theta of N? Uh you can uh you can just prove that from the definition, no problem. The the the trick here is we can often pretend that theta of a function is something like asymptotically equivalent to that function times a constant. We just don't know or don't care about what that constant is. Uh but there are cases like this one and like the sign one where there is just no no constant.

45:39 If you plotted in this case, so this is the the actual value for C, and this is uh well, what what gets from uh I guess log N and log of 2N. Uh then you get uh these two upper and lower bounds, so they nicely sandwich the blue curve. But, obviously, the blue curve is not a a constant multiple times any of those curves.

46:10 I think that's all I wanted to say about asymptotics. So, just to recap, it's it's a way of bounding one function by another, and it turned out the convenient notion is to ignore a prefix of the function, only look at values starting from some threshold value. And in many cases, ignoring constant factors is convenient. Uh but we can also do asymptotics where we include the the constant factors with the tilde notation.