Video 1-3: §1.3 Asymptotics

0:00 Intro

0:03 in this last section of unit 1 we'll talk about asymptotics and the big o notation that's ubiquitous in in algorithms and data structures so a last piece of mathematics that you should should know about i first want to motivate why asymptotics is useful and important in algorithms let me put myself over here um

0:30 first of all uh we want usually to abstract from unnecessary details at least at the the first approximation so algorithm analysis focuses on large inputs usually because that's where it shows where the limiting factors show what is the part of an algorithm that really falls apart if you scale it up to large instances this kind of approximation focusing on large inputs often also simplifies analysis i'll show you this example in a second

1:11 and the last point is a little more subtle but if you want to compare different algorithms it's usually inconclusive in that an algorithm that's simpler often is a little faster on very very small inputs just because of the lower overhead but then if you go beyond a certain size a more sophisticated and clever algorithm usually dominates and this turnaround point is usually for fairly small inputs so if you kept everything precise you would always have to say well if your input is if your array is less than 100 numbers uh this method of sorting is best but unlike you're in this in this very weird case that's not costly at all anyways you should really use this more sophisticated algorithm so it often makes a sensible comparison only possible to look at large inputs and focus on this part and as a concrete example suppose i made this example up so this is this is just uh i invented this function but suppose there would be an algorithm that had this as its running time uh let me just read it out so to make it a little more scary it's 2n squared minus 3n log of n plus 1 round it down plus 7n minus 3 log of n plus 1 rounded down plus 120

2:32 for whatever reason now an asymptotic approximation of that function in this case would be just the leading order term the 2n squared that is what's what dominates the growth of that function and you notice even though we have a fairly large constant here this offset 120 even if you go to input sizes 100 you hardly see the difference between these two curves they're almost on top of each other and whereas the black one is complicated has these little jumps and powers of two and all that kind of weird behavior the red one is simple to state is easy to understand so we usually like this one much better even though this is the precise answer for comparing algorithms this is is what we want

3:27 tilde notation

3:31 so that's why we want asymptotics now what are asymptotics there's different notations different notions that are used and i'll introduce them to you we'll mostly make use of of only some of them but i think it's useful to know all of them the first one is the the so-called tilde notation this is the strictest one it says two functions are asymptotically equivalent written like this f tilde g and here um that's the definition so this is this is true if and only if this is the case so that's my my definition uh you take the quotient of the two functions and you take the limit as n goes to infinity and that limit has to be precisely one the example from the last slide was like this and i actually used the tilde notation here if you uh if you paid close attention here

4:32 that's a very strict notion of equivalence and in particular so this this preserves constants constant factors i should say now if you remember earlier my comment about constant factors if we go back to the ram model we implement an algorithm in pseudocode not specifying the exact ram program then we often have different constant factors that come from slightly different implementations of the pseudocode down on the level of the ram program so often we don't care about these constants it's true that in my personal research i often care about the constants if you count dominating operations but still it's it's conventional to often ignore those constants

5:25 big o

5:33 and that's why people have invented this big o notation and that one's the more widespread notions so this is this is definitely what you have to know because it will be used all over the place in in documentation of programming libraries in research papers on algorithms uh and everywhere else this notation is more specialized um i think it's more useful often if you're able to show it but uh it's also simpler just to to state and to prove but you need you need more attention in the analysis and sometimes that's infeasible okay so uh that aside the big o notation f is in o of g that's how you write you read it it's defined as this i'll go to the definition in a second but i want to make this remark um formally big o of g is a set of functions a class of functions and you can make a statement that f n one function is a member of this set of functions now uh probably because in the typewriter area uh era of papers people had a hard time typing this element symbol it became customary to write equal here even though that's uh formally speaking just nonsense it's not it doesn't type check it's the same as saying 5 equals the set the set five

7:05 five equals the set of odd numbers something like that doesn't make really sense but it became so customary that you will see it all over the place and i might have used it on the slides even though i tried not to it's just everywhere so be uh be prepared for this and notice that this is a one-way inequality you can say f is o of g but uh not the other way around we'll we'll come to that so what does it mean that f is in o of g of n it means that i take the same quotient as above but now i only require it to be bounded so what i mean by that is it's less than infinity and i take absolute values to include negative functions as well and it should be bounded uh starting from some initial value for n the reason for that is uh

8:12 g of n could be zero and if that only happens for a finite number of cases we don't really care then we can set our r and zero bigger than that and we never divide by zero if g is exactly zero we do run into problems so it doesn't make sense to say f is o of zero that's uh as dividing by zero doesn't make sense uh you can write the same you can write the same thing as a lemus superior if if that makes life easier for you but if not you can ignore it so that is the most um the most important part this big o and its definition that's the the key notion um but there's two others that are also heavily used one is the the big omega and here i wrote the equals again this this really should be an element to make sense it's the same argument as before f is big omega of g if well the other relation holds g is in o of n o of f and we have the big theta which combines both f is in o of g and omega of g

9:33 and then i'm in the way here there's a third variant of this and that's the last one i promise that's the little o that's like the big o but it's stricter it means that f divided by g goes to zero if you take this limit and there's a little omega that goes hand in hand with this these are the formal definitions we will not usually use them a lot but you should remember that it's all about taking quotients that's the definition now uh what does this actually mean and that's probably more useful to you um okay let me tell you turn myself off the intuition behind this is the intuition behind the statement f of n is o of g of n is that f is at most g of n asymptotically so up to constant factors and for sufficiently large n so in the picture here there's there's a function f of n the red one and there's the function g of n but multiplied by some constant c we don't say what that constant is it could be fairly big but it's fine if there is one constant and there must be some threshold parameter some some value n0 from which on f is always at most c times g of n so it's an upper bound

11:02 it's a little bit like saying f is less or equal g but this has to be taken with a lot of quotes because it's at most g of n up to constant factors and for sufficiently large n only and then theta is is related to that it means that f is essentially the same as g but again up to constant factors and only for sufficiently large n so here the picture could look like this there's a the function f again and the same function g multiplied by two different constants a small constant and a big constant and then f has to be sandwiched between those two functions at least starting from some initial value before that it can do arbitrary stuff

11:52 Warning

11:52 now these these intuitions um the intuitions with these plots is definitely more memorable and helpful to keep in mind i just want to warn you a little bit uh so here's an example that i i prepared but you can you can click in the slides sometimes looking at plots can be very misleading and so let me just show you this very briefly

12:24 um so here's a plot now you can you can arg you can guess whether the red or the blue function is asymptotically bigger and if you go up to 2000 it looks well green is bigger first but then red definitely takes over right it's uh much steeper and if you go to 10 000 yeah red is gonna win and if you go to two hundred thousand whoops uh green seems to win by a fair margin and red is going very slow

12:59 and for these functions that i chose here if you if you're interested in the details doesn't doesn't matter so much it's a mathematical curiosity but if you if you keep going you can go as far out as you want it will always switch back and forth the answer in this case is red and green are growing in the same way they're essentially equivalent but at any point in time one is looking like it grows much bigger than the other one so it's a it's really care it's really um dangerous to look only at these figures that stop at a certain end because you can't really draw them for it to infinity whereas asymptotics make statements about infinity so that's um a piece of warning now a little question for you guys to test your understanding about this

13:43 Question

13:55 if we have a function f and we know it's in o of g what does that say about g what can we say about g okay results are coming in 12 people voted i'll give you another

15:15 okay if you haven't cast your vote do it now five four three two one here are the results and as you can see uh the second answer seems to be your favorite and that's also correct but there is a cave yet uh the last answer is is also not wrong either and the reason for that is if you don't say anything about the two functions we can only we can only make this statement sensibly if f is not zero so in a sense also the last answer is correct but for a nitpick reason this is really the uh the usual way is if f is in o of g then g is in omega of f because that's i again the intuition from this from the plot is f is smaller than g that means g is bigger than f right that's that's the usual um intuition

16:17 Example

16:21 okay i want to show at least one short example but without spending a lot of time how to do this so here's one statement is that these two functions are asymptotically equivalent this long term and just the the first sumand so what do you what you do for this is you take the one function the long one and you divide it by the second function

16:51 and okay i should have left a little more space here and then you take the limit as n goes to infinity now what is that in that case well we can just split this up it's the limit of

17:14 20 n cubed divided 20 n cubed plus the rest well that's obviously one and the limit of that so it's one plus the limit of of these things so oops

17:41 10 n log n plus 5 divided 20 n cubed and if you're somewhat familiar with limits you know that this is uh this is going to zero just because uh these functions grow much faster than the other ones we should have made this bigger and a way to compute these limits you can use well from alpha to enter the function divide by the other function and compute limits we'll practice that a little bit um for uh yeah we'll practice that for the for the first class test so uh even if you haven't had um detailed training in this or if your analysis class is long ago this is uh this is not a problem so that proves this statement because the quotient f divided g in the limit is one plus 0 right you can also make the same statement about just n cubed remember for that what we need is that so the theta means we have to show o and omega and for o and omega we have to take the quotient and show that it's bounded

19:08 so if we do that here we can do the same computation just that now for that part we would not have the 20. so this would be 20 but that's clearly bounded this would still be zero so 20 is less than infinity

19:30 so that would imply that this long function f f of n is in o of n cubed and you can show if you flip the two if you flip this around you can show the same thing for omega and that together implies uh the theta n cubed

19:59 let's do one more example briefly here so for the second one we have this f and this g um if we take this first of all uh you can take the two out of the log that's just applying oops uh applying um the logics applying the the rules for logarithms

20:34 so you get this now you want to divide f by g as always okay i should have been more careful here with this um i'll comment on that later and uh similarly as here you see that these are of of same growth so that will in the limit go to six and if the the limit is just a constant then you have shown theta immediately because you can flip that constant around if you flip these two then the limit will be one over six and that's also bounded away from infinity so you've shown this and this one's even easier to show but i might show you the might show you the limitations of asymptotic notation because clearly stubborn google

21:29 it's a huge number and it's still constant so we would often ignore it as uh treat it as a small thing all right um one more example for you guys uh try to apply the same reasoning and this is basically testing if you can follow along with computing limits

22:19 i should say you will have uh on the tutorial problems that are that are coming out now and they're already on the website but they're to be discussed next week you will have extensive opportunities to practice computing asymptotics and comparing functions in terms of their asymptotic growth so if if you haven't seen this before um you will have plenty of opportunity to learn it and it should be it should become clear

23:02 okay um i don't want to go over time so let me show the results here and uh of course that's correct uh the majority got it and um the reason is just uh the sine of n is bounded by um it's bounded in an absolute value by plus minus uh one so in this is if you divide that by n squared the n squared just goes and then the the quotient is just bounded okay well done uh here are a few um key facts about asymptotics that um often used to compute with it um if you have a constant times a function you can just drop that constant in and you're still in the same theta class that's true for uh if that constant is not zero if you add two functions that's the same as taking the bigger of the two functions that's a bit weird it would not normally be true that this is equal but if you're ignoring constant factors and only look at the asymptotic growth the two theta classes are the same one piece of terminology that's often used order of growth usually means the theta class

23:32 Key Facts

24:27 um it's not universally agreed but most people use it like that and here are a few typical orders of growth that appear and and the english name for them we have logarithmic and note here that if the base of the logarithm is a constant that it doesn't change the theta class as long as these are both positive constants the theta class is the same and we have linear uh linear rhythmic well that's uh okay i call it like that if it's n times log of n uh quadratic is clearly standard and uh polynomial is usually taken to mean n to the c for some constant c and then you don't specify even what the constant is an exponential is c to the n for some constant c well usually uh bigger than one otherwise it's a shrinking function and uh unlike for the opposite as for logarithms if you change the base you do change the theta class if that's an exponential function okay you probably have seen this if you've done asymptotics before or some algorithms class and if not this is like the most important rules that are used for computing with these um i want to finish this section with a small concrete example which also comes with a little bit of

25:56 a warning in terms of substituting intuition for the definitions and um that's the this well it's a certain algorithm it's a certain algorithm shown on the left that computes x to the m for some integer m it's called the square and multiply algorithm it's not so important what it does uh but let's briefly look at the code it takes it takes some um it takes a base that's the the x and it takes the exponent given as its binary representation in terms of bits then it iterates over those bits and whenever that bits one it multiplies the base with that and it always squares by well multiplying the result with itself okay so it always squares but sometimes also multiplies

26:50 i want to count the number of multiplications that this algorithm does it's a it's a useful algorithm it's it's a real world application of of asymptotic analysis so uh we should be able to do this right um if you if you do this carefully you see line four this multiplication is always executed whenever you go through one iteration of the for loop that's n if well n is the number of bits in in m okay

27:21 and then we have additional multiplications from line five well how many exactly as many as there are one bits in the binary representation of m okay how many bits can be one well at most all that would mean c is at most two n and uh well at least no uh none then we still have n okay so far so good um

27:54 Question Answer

28:00 and here i left it open answered so the situation is as follows we have this function c of n and we've shown it's at least n and at most 2n what does that mean what's the most pre what's the most precise asymptotic statement that we can make for this function in that case and i just opened it as a as a word cloud so you can you can pop in any answers try to write it in ascii math um

28:30 uh what do you think is the most precise statement that we can make about c of n knowing this uh this kind of bounce a lower and upper bound of n respectively 2n

28:56 switch to the answers there's a lot of stuff floating in and uh yeah you can see the answers as well so there's a big um i mean the the the bigger this answer becomes that means uh it's been answered by different people um and the biggest is for for o of n uh 2n is not really an asymptotic statement i would say maybe tilde 2n but that's not necessarily true and theta of 2n that's the same as theta n isn't it

29:46 okay different versions of writing of n o of nothing that's interesting maybe it was a typo theta n yep okay because we're running a little out of time let me just move on but you can you can keep typing it in um the i mean there's the answer that most of you that um got the most votes was o n and that's not wrong but it's not the most precise statement that we can make and the answer is indeed theta of n we have a lower bound and an upper bound which is both

30:36 linear which means uh the theta class is n you can show c as at least n that gives you an omega n you can show c is at most 2n for all n actually so it's a an o of n and big o of n big omega of n together is big theta of n so that's the right answer and you can express this in terms of the size of this number if you want so uh c is theta of log m where m is the the value of this exponent and if you plot the actual cost for this number if you take the actual number of one bits in the representation you get this really nasty blue graph which is i mean it jumps up and down and it's uh well it's i mean it's an integer function it's not continuous anyways but uh yeah it does weird things um and the lower and upper bounds here that's the um the log of this so it's log n and 2 log n i guess um my important carry out here is usually you can pretend theta is just like tilde but with an unknown constant

31:51 but in this case there is no such constant it's not that c of n is tilde to some constant we just don't know the constant uh as this graph shows there is no constant we can only show upper and lower bounds so there is no tilde class for this function except itself maybe but there is a sensible theta class so that's another motivation why we like the the order of growth asymptotics and the or the theta classes sometimes better than the precise functions and even the more precise asymptotics because it could be just there is no no concise way to write a function in that way