Video 1-3: §1.3 Asymptotics

0:00 <Untitled Chapter 1>

0:03 so in this last section we'll look at asymptotics big o classes and also motivate a bit why we want to have this tendency to make things grow to infinity

0:17 so let me start with why do we look at asymptotics uh as a as a fact algorithm analysis usually focuses on large inputs and by large i mean sufficiently large for certain statements and that can be really large and the reason for that is uh is three-fold first of all it abstracts from some unnecessary detail many many algorithms need to treat very small cases slightly differently from the general case again something that might make more sense on examples and how you exactly deal with these little uh little base cases is not usually that interesting or important and um a formal way to to say what we that we want to ignore those is to look only at large inputs it happens to simplify the mathematical analysis of algorithms something we'll come to and the reason you can already look at below and the third one is for the the other task of algorithm analysis and all these modeling efforts was to compare algorithms when we have several algorithms for the same algorithmic problem we might want to know which one is better and [Music] as just was also the topic of some questions sometimes these measures contradict and so you have to decide which way to go and one way they can often contradict is algorithm a is fast

1:53 on inputs up to 100 but then for bigger inputs algorithm b is better now it depends on the application if you actually have many many calls to tiny inputs then maybe algorithm a is interesting but most of the time this is not the dominant cost in an application so instead you want algorithm b which is good on big inputs so for making a proper comparison between different algorithms and make that comparison conclusive we often need that assumption that we look at large inputs

2:30 asymptotics is all about an approximation when something gets large when a parameter gets large in our context we will always think of the input size n going to infinity so it's always an approximation for n around infinity you might be you might have dealt with approximations for functions in some other contexts i don't know engineers often use taylor series approximations to functions around a certain point this is what your calculator does if you call the sine function or the logarithm function they all use some taylor series expansion which is an approximation of a function which is complicated by some simple function around a certain point and computer science does the same it's just that we use this around infinity so the techniques are sometimes a little different and to motivate this more concretely let me look at this function so let me read this out to make it sufficiently scary suppose there was some algorithm that has the exact running time f of n where f of n is given by 2 n squared minus 3 n and then the log to the base 2 of n plus 1 rounded down plus 7n minus 3 times log of n plus 2 plus 120 i mean for whatever reason but stuff like this is sometimes the

3:55 output of a precise analysis if you go count the exact number of instructions on the word ram uh some people have done this like uh like one standing in front of you uh but this is this is a i made this example up but we can maybe agree that this function there's a as a plot is kind of ugly and nasty to work with whereas a nicer function is just 2n squared and here's another plot so the red plot hope you can see the difference the red plot is for the red function a very simple function but it well approximates the black one and you see in this case i just had to take the this first semant and it happens to be a good asymptotic approximation for that function that's the kind of simplifications we're after we try to make the function that's otherwise complicated has these these jumps at powers of 2 or powers of 2 minus 1 and so all of these weird things that happen in the original function and we replace this by a much simpler

5:08 Asymptotic tools - Formal & definitive definition

5:11 so let me formally define what asymptotics for us is we'll not always need to work with this definition but i think it's very important to have one concrete formal definition of this on the slides so bear with me for a second we'll do an example after

5:31 i'll start with this simplest version of asymptotic notation which is the tilde notation so f and g are asymptotically equivalent written like this if when i take f divided by g and compute the limit as n goes to infinity the limit is one that's the first the first thing and then i would like to treat these two functions as asymptotically equivalent because they uh they give the same value for large n and and you might notice i use this tilde symbol here and this is not by a coincidence those two functions are asymptotically equivalent

6:16 a more widespread use of asymptotics is the big o notation i'm sure you will have seen this so we define a class of function o of g of n is really a set of functions and so the proper way to say f is o of g of n would be to write element because f is an element of this set of functions but pretty much all around the world people write equals i think this has historic reasons people started typing algorithms papers on typewriters and it was just absurdly inconvenient to write so many element symbols it's mathematically bogus and it confuses uh first-year undergrads all the time but i mean you're msc students so you can probably deal with it um i put an element sign on this slide but probably for the rest of the module i'll go to the convention that the rest of the world follows you'll have to live with it so we say f is in o of g if again i take the same quotient as before but this time i don't require that it converges to one i require something weaker i take the absolute value and then say that this remains bounded another way of saying this quotient doesn't go to infinity okay

7:42 and you can also write this using lim superior i don't know if this helps you at all if it does great if not you can ignore it the important part here is we allow up to a certain value and zero that this is not even properly defined it could be that that g is zero for a while or something like this uh we want to ignore that but up starting from a certain value in zero this quotient has to stay bounded has to stay below a certain value in absolute terms

8:20 all right i guess you've seen this but maybe not exactly this definition and i think this is a good definition i'll show you why there's two variants of big o big omega is the other way around f is omega of g if g is o of f and big theta is the combination f is in g in in theta of g if it's in o of g and omega of g so then they're in a different sense equivalent asymptotically but not as strictly there's well we'll come to that um there's a third version of asymptotic notation that uh i think you will sometimes encounter that's the little o and little omega and that's that's a stricter version so here we say that this quotient has to go to zero as opposed to just stay bounded not go to infinity now it has to go to zero exactly okay

9:22 um for most intents and purposes you can replace this formal definition with this intuition but again in case of doubts go back to the formal definition f is o of g means something like f is at most g but with a caveat or two

9:52 Asymptotic tools - Intuition

9:52 just in quotation marks so f is of g means f is at most g but up to constant factors so i might have to scale up g by a certain constant but fixed not depending on n and only for sufficiently large n it might be that they do whatever up to a certain point but after that f stays below c some constant times g okay that is big o um and of course you can derive this from the definitions but because we'll use those two mostly uh here's the picture for big theta that means f is roughly equal to g of n but again same two caveats up to constant factors only so i can bound f by g from below and from above if i multiply with a certain constant and i mean obviously c1 will be a smaller constant c2 will be a bigger constant and again this only has to be true up to up from a certain point on or sufficiently large n okay so that's the intuition you can often just look at pictures like this and guess what the asymptotics will be but i want to point you to a really nasty example

11:13 that maybe shows why these things are not always quite so clean uh you don't have to read the text what i want you to look at is this plot of two functions the green and the red one and uh this goes up to 2000 and up to 2 000 and it looks like okay initially green is is bigger right but red has a higher growth so a higher slope so it picks up and it seems like from this point on red will be bigger and it looks like it will be substantially bigger from then on if you zoom a little further out up to 10 000 this indeed seems to be confirmed okay so here we have the point where they turn over and this seems to suggest yeah red just grows much bigger than much faster than green but if you zoom out further to 200 000 uh look how they flipped again so there's another turning point at around 50 000 where the two cross and now certainly looks like the green is growing much faster than the red one right um and this is these are two concrete functions here they are they're nasty they're made up it's an example that's contrived if you look at a doubly logarithmic plot you see what's going on the two are

12:40 oscillating around each other and they're actually asymptotically equivalent their limit goes to one but from just looking at these plots it doesn't look like it so be very don't trust the plots only trust mathematics or limits rather but still in in most cases you can you can write down conditions on the functions if they don't do this weird oscillation you will not see this kind of behavior so there are many special cases where looking at the plot like this is sufficient uh just in general be careful all right

13:27 if you have questions you give me a shout let's do a quick test if you're paying attention and or know this already okay numbers are shooting up give you one more second this is not supposed to be a mean question it's one of these are you guys awake uh i also notice here i use the element symbol here and then the equality down here this is not where i'm getting at i should have been consistent on this on this question

15:00 just shows how deep this is uh contained in in me as well that these two things are the same uh so let's say we lock it here and this is the the intended answer but i also give you a go for the last one for a reason i'll come to in a second uh if f is in so let's let's just go back to the the picture briefly

15:26 the way to think about it this question just tests your understanding on on this intuition if f is o of t that means f is essentially smaller than g with the two caveats right up to constant factors sufficiently large n so if you flip this around if you ask what is g in terms of f then g is bigger than f and the symbol for that is omega so this is essentially what i wanted you to answer but if if f is identically zero for example then you might say zero is in o of g or some functions that still kind of makes sense but nothing can really be in omega of zero in a proper way because you divide by zero this is a okay it's a bit of a corner case if this is what you had in mind by ticking the last one well done uh uh pat yourself on the shoulder uh for catching this this little corner case uh if not you can basically ignore this unless there's some something broken with the definition division by zero uh the intended answer is the second and it's just this if one is smaller than the other then the other is bigger than the former okay

16:45 let's do a quick example just to see why i like these definitions that i gave you over some others so the alternative that people often give for f of n is in o of t of n is there is sum and 0 and then for all n greater and 0 this function is less than c times that function stuff like this i think this is fine but there's there's nerdy nitpick reasons why i don't like that and there is the practicality issue if you want to test something like this is this this nice function 20 n cubed plus 10 n log n plus 5 is that in theta of n cubed or is that tilde n 20 n cubed what you really do is compute the limits and that's it you don't mess around with finding n0s so let's see we take the long function and you have to check if i'm computing correctly this time

17:16 Asymptotics - Example 1

17:48 unlike uh that little thing on last week that's my f and that function that's my g and i'm testing now whether f is tilde of g okay that's the first thing we want to prove so i'll take these two and i compute the limit as n goes to infinity now the easiest way this is a fraction where we have a suman some summation in the numerator so we split this so we have 20 n cubed divided 20 and cubed that's just one and we're left with another limit

18:45 and you can show that this is zero in various ways but this is this is basic real analysis now i don't want to go into that there is a tool well from alpha just in case you're not sure now that brings me to the question on on this sign we will eventually have an exam i have yet to learn whether that will be an online exam or an exam on campus the only thing i know is that it hasn't been definitively decided yet if it's online there's no way i can stop you from using well from alpha so i would allow it i allowed it in the past years if it was on campus there's no proper way to allow it without allowing you other things so i would not allow it but then make the tasks easier either way if you want to be sure for the exercise problems you can use well from alpha to compute limits because again we're not a real analysis class this is about practicing the asymptotic notation so i'm fine with you using this and limits like this either you know it by heart anyways that n cubed dominates n log n uh or you compute the limits and well here you want to use l'hopital's rule and

20:03 it's not complicated but not not what i want to spend time on okay so we proved we proved this part the tilde part i can take the same proof basically works if i do away with the 20 let me just make that gray and then

20:26 this would turn into a 20 but the rest would be the same so now i have divided this f by a different g and the outcome is 20. the limit of this quotient is 20. so if you go back to the formal definition

20:49 uh for for big o first we divided f by g and we got 20. 20 even like an absolute value remains 20 and it's definitely bounded it's for example below 21. and so we've shown that f is in o of g

21:09 so we this part also proves okay now we would also have to do the omega part but that we have to take the quotient in the opposite direction we divide g by f uh so if you do that with this limit everything flips over and the result is 1 over 20 but that's still bounded and so we also get

22:02 if you've done asymptotics before bear with me i know this is like a baby speed in a way but i want to have i give everyone a fair chance to learn this before we use it all the time

22:19 so that proves o of air f is o of g f is omega of t together big theta of g so that that proves this part as well okay

22:31 let me briefly do this the second example so we take again the first function divided by the second now you may remember if you have an exponentiation inside the log you can pull it out as a factor so that's the same as 3 times 2 log n plus the log log n and then we divide by log and here you may note that uh i didn't put the base of the log here so if i write log that's something to point out maybe lg

23:10 always stands for log base 2. we have a special symbol in computer science because we use it all the time guess why ln is the natural log base e we don't ever use log base 10 so i don't have a symbol for that i do use log without anything only inside big o classes because as we'll see it doesn't matter which base you take as long as it's constant so it's uh that's that's my notation it's not completely universally agreed upon but if we do if we divide by log here we might as well take uh any base as long as it's constant so we can convert it to base two

23:52 um and so again if we take the limit of that you notice you can write this as 6 plus log log n divided n if i take the limit that's zero so let me cut this short here again something you can check with wolfram alpha or you take l'hopital's rule twice and then you're there um and so the quotient remains bounded because it's six so that proves big o if i take the reciprocal the quotient the limit is one over six which is also bounded so i also get the big omega and together that's the big theta same as before

24:42 and the last one doesn't even need a proof it's just there to point you to something that's somehow a little absurd i think that number is called one google where google got its name from legend has it it did but it's it's just some number it's an absurdly huge number but of course if i divide it by one it's still an absurdly huge number that doesn't change doesn't grow with n so it remains bounded the quotient remains bounded so this statement is correct it also means if we're using asymptotic notation in particular the the theta classes big o classes we're ignoring constant factors which could be one google which might mean that the statement is is very very crude luckily in most cases most algorithms this these constants are not that bad and so they make proper statements but there's examples known in in rare exceptions where indeed the constants you're ignoring are so big that you shouldn't ignore them most of the time we're lucky and if you're in one of the unlucky cases you should try to prove a tilde result instead where the constants are not ignored

26:05 okay let's try another one just real quick so it's sine n plus 2 times n squared and theta of n squared anyone still busy i think there's a few people left ah boats are trickling in okay

27:35 so most of you get this right uh the the thing is you divide switch back uh it's true um and the reason is you divide the sign n plus 2 n squared divided n squared take the limit of that

27:43 Clicker Question

28:01 that just cancels now you can't really compute that limit right it's a it doesn't converge um so this is one of the cases where you work with the actual definition um and you can still say sine is never bigger than one even in absolute value terms and the plus two so this is never bigger than three and also um it's never less than minus one so plus two still makes it one so this quotient for any n is between one and three and that's enough to show that the quotient is bounded and the reciprocal is bounded so that gives you the the theta statement okay so that's one example where taking limits doesn't work directly however if you type this into wall from alpha it wouldn't just say ah i'm broken i can't deal with it this doesn't converge you would actually say the limit is the range from one to three it's pretty smart in this sense that it still gives you a reasonable answer which is good enough for answering this question

29:12 Asymptotics - Frequently used facts

29:16 um this is a quick cheat sheet of of useful rules how to work with these antarctic asymptotic notations uh just very briefly if you have a constant factor you can ignore that in theta classes if you sum up two functions in theta that means the same as taking the bigger of the two

29:42 and here are a few um often occurring orders of magnitudes or or theta classes you can have logarithmic as i said before any constant base of the logarithm doesn't change the theta class because you can just pull it out as a constant factor linear is something that often occurs and again constant in front of it is ignored linear rhythmic is a bit of a portmanteau of linear and logarithmic it's just n log n right uh quadratic sometimes yeah and you will often hear in in other contexts in complexity theory people talk about polynomial time and exponential time as the big things to contrast and here's the formal definition for those two but we won't really need this much because we're focusing more on the efficient algorithms that's mostly a cheat sheet for you to come back to

30:38 Asymptotics - Example 2

30:40 i want to finish with a last little example and then we should have a few minutes left to briefly look at the prior knowledge survey so last little example on asymptotics uh that combines two things it shows an actual algorithm and it gives us another little

31:02 corner case caveat so this is uh this is an algorithm for computing x to some integer power so it's computing a power uh now you could of course take x and just multiply with itself m times now uh it'll depend on the word ram how big the numbers are uh what how long this takes but i want here to say let's keep things simple we only look at the number of multiplications okay so our cost model here is is a bit more abstract we don't care how big numbers get and of course if you just multiply the number m times with itself then that would be cost m or minus one and this algorithm can do it a little smarter so this is written in java code but i hope this is understandable even if you are not very familiar with java so this is x we pass in x and we pass in m in binary we already split off the binary representation and so what this algorithm does it starts with one and for every bit it always it iterates through the bits of m it always multiplies the result with itself which means it squares it if the bit is one you also multiply with x okay and you can think about that this always

32:32 works and computes x to the m correctly and how long does it take well roughly um we'll we'll see in a second so first of all let's let's um give some names to the input parameters let's say m is the number of digits sorry m is m is the binary number this this number and n is the number of bits in n in m ah and x is given as some floating point numbers so we assume that this fits in one word and so then we only have to compute the number of multiplications so how many multiplications do we do in total we'll run through this loop n times so that gives us n multiplications from here

33:21 and the second the second time we do multiplications is in this if case so well that depends it's the number of one bits in the binary representation of m that's the second suman that's the additional number of of multiplications from here

33:40 well okay there's line five already written maybe that's enough so what we can easily see is that the number of multiplications is between n and two n okay because this the number of one bits it could be zero or maybe one uh but let's be generous uh it's at at least zero and at most n because n is the number of bits in m overall and if they all won then this is the maximal value

34:11 so now i would like to ask you what can we deduce from this knowledge and this knowledge alone i think it's insightful to post this question so let me give you a minute it's the last slide anyways so worst thing is that we don't have as much time to discuss the the prior knowledge survey i think that's okay

35:46 so what i mean by uh most precise synthetic statement is one of the the things um so c of n equals and then something or tilde or something and you should give me the most precise you can think we we can make

36:08 it's a little a little tricky it's a bit more than what we've done before okay um many of you voted for theta n uh and that's that's the answer i was after

36:45 just give me one minute to make that last point so this is the correct answer theta of m um sorry theta of n which is theta of log m uh here's the plot of the of this function the blue one so place this last point down here is important we can usually think of theta meaning that one function is asymptotically equivalent to another function times some unknown constant and we don't care about the constant except in in some cases uh there is no such constant like in this case you see this blue function definitely is not a constant times the red or green it oscillates between the two and this is allowed for theta so theta is sometimes more convenient not just because we ignore the constant but we can't actually nail down any constant