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

0:00 Introduction to asymptotics

0:01 the last subsection we'll talk about astics and Big O notations uh because that's the way how computer scientists usually Express statements about the efficiency of algorithms and it's it's a useful approximation and just a piece of vocabulary that you uh that you need to know if you talk about algorithms to people but instead of just showing um uh let's let's see uh how people are on this uh I'll I'll decide a bit on on your answers how quick to go I don't want to bore people with things they already know but also I don't want to go too fast uh for anyone who's not seen this much

1:10 I'd love to see 100 votes but I don't promise I'll wait for uh it no matter how long it takes I'm a naturally impatient all right I think that's that's good enough for seeing seeing the rough picture uh so we have a majority who knows who knows this but there's a substantial bar below with the I don't know Big O at all so uh let's have a look at that

2:09 and also for all the others um I'll I'll we'll come back to this so no no real explanation on this I want to motivate a little bit why people use astics before we dive into this I'm not sure if that's very very um very prominent or very very uh obvious to

2:12 Why use asymptotics?

2:29 anyone the key the key thing why we use as is because the analysis of algorithms focus on large inputs and the reason for doing that is if you're if you're just concerned about small inputs maybe there's a way to just uh list all the small inputs you need or you do extra special cases for small certain specific small inputs so by focusing on large inputs you can you can abstract away from special casing just a bunch of different cases uh focusing on large inputs then also simplifies the analysis because uh certain cases the certain boundary conditions uh don't play much of a role well we'll see examples for that uh and sometimes you need to do this because uh one algorithm might be better for uh small things and then might go slower and another one might be better for larger things and generally we think of the second algorithm as better um one way to think about this is uh if I ask you what's the fastest mode of transportation to get from point A to point B it's really an unknowable question if that is from here to the door I'm probably faster than any any mode of transportation just just run right if you start laying down a train track and in five years time or well this is

3:55 England right maybe it will never be built but uh let's not get political so maybe you lay down this train track and you start your train and it'll speed up and uh well stop right away that's not a fast way of traveling but ASM totically if the distance is from here to London I don't want to walk and uh if you have a train that's probably a good way to go it's probably the fastest way to go right um so that's that's why we why we focus on large inputs or in this case large distances if you want to know what's the for large for with the Parts where it matters because overall the cost will grow with the input size so the big inputs are those that you need to get right uh for those you want to focus on and you want to find the methods that are effective for those mathematically speaking astics means we look at an approximation of a function around Infinity that's a a an informal way to State it and here's an example that maybe illustrates the point this is one Long Function it has has a parameter n and it tells you for example I've made this one up but maybe there is an algorithm that has that running

5:06 time and uh it's a very long term it looks complicated and it's not really clear how fast it grows you have to look very closely before you see it h here's a here's a graph of the function you see that has these weird jumps at powers of two and all that all that nonsense um but there's a a much simpler much smaller function smaller term for a function uh that captures the growth of that function very well and is much simpler to write down and to understand and in this case uh this will have a precise meaning this this little Tilda symbol that's the kind of astics we like they take away the complication from a function and leave the important bits but are easier to interpret

5:55 Formal definitions

5:57 okay I'll jump right into the formal definition of what the standard as totic notations should be defined like now caveat not everyone defines them like this but they're mistaken uh I've been working with these for for many years and is that's the definition that causes less least trouble trust me and we can debate it offline if you want first notation is the Tilda that we've that you've just seen and we say two functions are ASM totically equivalent or F is Tilda G

6:36 uh exactly when their limit converges to one if you take if you if they're quotient converges to one so you divide one function by the other and take the limit for n to Infinity

6:53 okay the more widely used relatives with this big O is defined somewhat similar but it's a bit vague a bit looser so we say f is Big O of G if you take F and you divide it by G and that quotient is bounded so it there's a there's some number so that this quotient stays below that number for any n at least for any n up to uh starting from some point but uh you can you can uh leate that there's a second definition if you can read that then fine otherwise ignore it it's the same uh note that Big O should really be a set of functions but it has become customary to write an equal sign where it should really be an element sign you just have to deal with it uh what it really means if you write something like this is what's here on the right the quotient is bounded that's the formal definition anyways there are two variants there's big Omega which is the opposite f is an Omega of G if G is an O of F and and there's big Theta which combines the two so f is in Theta of G if it's both in O of G and in Omega of G these are the formal definitions and

8:11 they're most useful for uh for checking in details there's one more less known cousin of these the little o f is in little o of G if the qution goes to zero and the opposite is little Omega these are the formal definition that are useful for checking they're not intuitive though so let me also give you uh the more pictorial intuitive notion which 90% of the time gives you the right answer but you have to be careful that there are some Corner cases where it doesn't work um f is O of G is essentially the same as a version of f is less than than

8:33 Intuitive understanding

9:07 G and Theta would be something like similar or equal and Omega would be greater equal but but but f is less than G up to constant factors and for sufficiently large n so if I take my function f it might do some might do some weird things for a while but then there's a cut of point from which on it be behaves more more stap so that if I take my function G and multiply it by some constant number it stays above the function f right that's what the definition says and you can you can check how that matches the quotient limit and so on if you

9:55 want I'll I'll come back to uh that example um for for Theta it's basically combining two two things you can sandwich your function f between function G multiplied by a small constant and function G multiply it by a bigger constant and again before a certain threshold the functions can do whatever but after that they stay in the right order okay so morally you should think whenever you read f is O of G you would you want to read this is smaller f is smaller than G but with the caveat that it might be only up to concent factors and only for sufficiently large n

10:34 okay uh we could have a little fun with that example maybe let's let's skip this you can look at the slides don't use plots like these for finite n to decide astics you can horribly be mistaken and there's a nice example that I duck out years ago um just to illustrate that point not so relevant for now let's see if that has sunk

10:59 Notation and implications

11:41 or if you're hardcore you want to see the definitions it's fun to watch the little bars go up and down I know you can't see it but right in the interest of time let's move on uh so uh here's here's that uh I'll comment on it a bit again resist the urge to change your answer now it's not really uh not gaining you

13:15 anything so answer B is is what is essentially the right thing if f is O of G again think of this as essentially meaning f is less or equal

13:39 now again remember what what do the quotes mean the quotes mean up to constant factors and only for sufficiently large n those two things you have to keep in mind uh but because we're doing this on both sides it works out like this now uh there's something to be said for the last point but that's a nitpick if uh IF function f is identically zero then you get trouble with the definitions by dividing by zero and so on but that's uh we won't deal with so many algorithms that have cost zero straight out for all inputs so it's mathematically speaking this is only true if f is not exactly zero the zero function that is zero at every

14:28 Calculating complexity

14:30 point why did I present you the uh definition with the quotients because after all that's uh if you want to check astics the easiest way to do it so let's have a um a few small examples uh on how how you use this so this first example okay has two statements let's um let's pick this statement this longer function is supposed to be in asically equivalent to this smaller function so we have a large function that's called f of N and we have this one let's call that g of n so the first claim is that

15:19 f f of n is ASM totically equivalent to G of n so if you look back to the definition I'm not going to do it because I know it by heart but uh you can go back what you should check is that

15:33 the limit of the two function should converge to one when n goes to Infinity so how can we check that the long form of this would be that now I'll I'll insert f and g

15:54 again 20 n cubed 10 L and 10 L and n + 5 that's a fraction with the sum in the numerator so we split it we have 20 over 20 n cubed over 20 n cubed that's otherwise known as one and then we have these other

16:45 cubed now for this last one is maybe obvious without thinking we have a constant and divite by something that gets bigger and bigger and bigger so that's zero well that one you may have to uh think a bit harder so we can cancel a few things uh here it's also still easy we can cancel one n with 1 n and log n is less than n so we can upper bound it by so let me do this in small we can say this is less than 10 / 20n because log n is less than n for large enough n and so again we have something that goes to zero there's other ways to do it if you have the quotient of two functions and both go to Infinity you can use lal's rule which means take the derivative of the numerator divided by the derivative of the denominator and then take the limit of that if you keep doing that a few times for all pols and logarithms that will resolve to the answer now I also uh respect the comment at the bottom here for this module is not an analysis class so I'm I'm fine if you use W from from alpha to compute limits I'm not really here to teach you limits it would

18:02 be useful if you were able to compute a few simple limits just because I think it's common common knowledge that is useful to know but uh if you have to use that now uh we can use the same calculation to also do this this second

18:29 part well I haven't explained that part so um so far we've only shown this part the black um black claim if we also want to prove this one Theta of n

18:46 cubed one One Direction so first of all this means two things it means f is O of of this one and Omega of this one for the first part we have to show that f ided n cubed stays bounded and uh We've proven that it converges to one so it is ASM totically less than one right so we have

19:26 uh We've shown that it converges to one and that means it is bounded there's an an upper limit you can put on the value of that thing and that already

19:45 implies and that already implies the the first statement now for the second statement we have to invert the two roles well luckily we can use use essentially the same statement if that converges to one that converges to the reciprocal uh and that's still one so it also means that this is

20:27 claim uh let's do this example as well at least part of it so again what do we have to do we have to take the quotient of the two functions and now you need to know the logarithm rules to work that one out if there's a an exponent inside the log you can pull it out as a

20:58 factor and I have to divide divide that by log n and now here I've done some some nasty things what does log mean without this LG LG will always mean log with base two in our context and uh inside the Big O it doesn't matter what the base is as long as it's any constant because all the logarithms differ just by a constant Factor if the base is different if the base is a constant so we might as well put a two here as well and then you can do the same trick um you can cancel the the log on that one and this one log log is less than log so it converges to something less than one so in this case it

21:52 converges the quotient is is six if you pick log base two here and so again by show showing that the quotient converges to a constant you've shown that this divided this is upper bounded and also the reciprocal this divided by this is bounded and that you've that way you've proven both both ways for for

22:26 again and this G and that's that's all we had to prove uh the last example doesn't even need a computation it's just uh pointing out some idiosyncrasies of these definitions that's a humongous number uh uh probably about the size of the universe in some measures the number of protons in the universe is probably less than that but it's still a constant so it's O of one because if you divide 10^ the 100 divided by one that's still bounded by 10^ the

23:20 100 so again if you have two functions and you want to check some some statement like this you take the quotient and compute the limit you compute the limit either using tools like w from alpha or the analysis one knowledge you learned either in high school or at some University class we don't really need any fancy limits most of the limits can be dealt with the simple rules that that you have learned there but it's not it's not the main skill I want to check I want you to apply the definition and conclude the right things

23:56 Advanced properties

24:24 call well we're almost done for this unit there's two little things I want to point out little other things little features of these asmic notations uh one is in this

25:11 voted all right so there you go uh in past cohorts it was almost equal but this time you you've done pretty well uh but quite a few people um also said no so why is it true that this function is in Theta of n^2 well there's actually nothing really weird to do you do the same as we did before you take the upper the first

25:49 function you divide it by the other F the function in the parenthesis and you study the limit of this right so obviously we cancel the n^ S so what's left is not a constant fact is not a number it's still something that depends on N that's why the definition doesn't say quotient converges to a number it says stays bounded famously sign is between minus one and one so it's it's at most one right so this whole thing is at most three and uh okay here it also becomes relevant for the first time if you remember the definition took the quotient and the absolute value uh just to make sure that in case things go negative positive uh we don't get into trouble uh but that's all we need to show so that means um the V implication sin n + 2 n^2 is Big O of n^2 and for the other direction we have to take the other uh quotient so because in this case we don't have a a straight limit we have to to do both at least in your head all right so we again cancel maybe could have skipped this time we again want to bound it's a fraction and we want to Upper bound the fraction that means we have to lower bound the

27:15 denominator sign is uh always at least minus one2 minus one so if I put in minus one here I get an upper bound let's do this slow minus1 + two and that's one okay so also the reciprocal the other quotient taking that function divided by that one is also upper bounded that the function itself fluctuates doesn't matter good L us caveat number

27:56 one this is basically just for you um as a cheat sheet there's a few rules all of those are fairly obvious if you if you go back to the quotient um if you have some some function and you multiply it by a constant that's still within the same Theta class because you just make the fraction the quotient a constant bigger but it's still bounded if it was bounded before more interesting if you take the sum of two functions that's uh the same Theta class as the maximum of the two again you can bound um you can bound the sum as two times the maximum and so on you will discuss in more detail uh in the tutorials examples on on how different functions relate uh these are kind of named classes of function growths that often occur in algorithms so uh that's why I listed them here other otherwise there's nothing special about them

29:00 Practical algorithm analysis

29:02 now I want to put uh I want to finish with one concrete example from analyzing an actual algorithm and seeing how how the ASM totic notations might help to express things in a clearer way uh what you see on the right is an algorithm to compute some number to the MTH power where m is an integer now of course there's many ways to do this and the algorithm is somewhat smart but it doesn't matter so much what it does uh but it it computes this without doing all the M multiplications it does this by repeated squaring uh but to make it work with any number M you have to do some trickery again as I said this is not really uh so important this is actual python code that's uh one way to get a list of the binary digits of a number in Python uh ignore ignore this this kind of weird stuff that's python specifics but you can do this if you have a number you get a list of the digits in the binary representation of the number then you start with one and then you iterate through all the bits uh you always do a multiplication and if the bit is one you do another multiplication that's the algorithm okay fine uh how fast is

30:22 it uh let's count the number of multiplications okay so there's one multiplication happening in line six and one happening in line eight I guess these line numbers have moved so this should be line six this should be line eight the overall cost if we have these conventions for the input so the number of bits in m is n then we have exactly n operations here because that Loop is is it is run through n times and then the other one we don't know exactly how many times but if we have the number of ones in the binary representation of n then we know that's just a bit unwieldy but it's obvious from this that it's at least n and at most 2 N

31:23 okay question from what we've shown here what can we say about this algorithm I want to stress here that we're after the most precise statement that you can make so there are many correct answers to uh what you can say about C but I want you to be as precise as possible without

32:33 all right I think you can see right I didn't show it yeah I mean just because it has the biggest blob doesn't mean it's correct right and yes I know slider supports smilees and emoji

33:05 she oh someone found out how to type a square root oh you copied it from no I didn't put it here fair to say that we have different answers the most precise one yeah I know this is deteriorating now so uh I'll let you have fun um but I'll I'll move on it's getting late I know so the most precise statement you can make is uh Theta n because you can both prove the upper and lower bounds so let's let's briefly go through y c of

34:00 n we have this function C of n now we divide it by n we don't really know what c of n is there's a plot which oh my God looks a bit crazy right it's not not a nice function but you can still upper bound this by the two n that we've had so that quotient is bounded by two fine and I take the other quotient n divided C of n then again I upper bound this this time using the lower Bound for C is very similar to the sign example we've seen before except that here there's not even a hope of specifying what C looks like precisely in in primitive terms um but I I can say this is at most one because C is at least n so I have proven both of the quotients are bounded hence the function is in Theta of N and I can't make a more precise statement with the Notions we've had I I can't easily say Tilla statement unless I have some some more concise way to express the function and of course you can express this in terms of M if you substitute that back in So my my last point from this is uh what's in the box down here usually it's good enough to think of

35:17 theta like Tilda with a constant that you don't care about right so f is roughly G up to constant factors and for large enough n but sometimes there is no single constant that makes this true it might be a case where the function weirdly fluctuates between an upper and a lower limit and you can still make this Theta statement but there's no there's no single constant that that you could stick to n that would make it ASM totically equivalent to F or c