Asymptotic Notations 101: Big O, Big Omega, & Theta (Asymptotic Analysis Bootcamp)

Key Takeaways

okay so for this video today we are going to have a discussion about asymptotic bounding and and bounding the asymptotic nature of our functions so I always say things like o of n or N2 but what do I really mean I I kind of addressed this in another video where I talked about what uh asymptotic functions actually mean and what these bounding mean but I think it's time to go very deep into this topic and get very detailed and mathematically rigorous about what I'm actually saying so before I continue on if you have not subscribed to the channel subscribe to the channel and like this video my goal is to make this one of the world's largest software engineering resources for preparing for interviews and this is a very large component of that understanding how to bound ASM totically so first let's look at our most common bound which is the upper bound which is the Big O bound and we're going to look at the mathematical understanding behind it and I will make it as simple as possible so that we can really understand what we're actually saying when I say Big O of n so okay the way that asymptotic bounds work and the way you really should think about this is every time you have a piece of code or you have an algorithm it requires resources these resources come in the form of taking up time or taking up space and our job is to analyze how much time and space does this algorithm take because that is of interest to us the more we can understand how an algorithm behaves behaves the better we can optimize it see where its flaws are see where we can improve things and we can improve its asymptotic uh nature so first of all I keep saying the word asymptotic what does that mean so asymptotic as you probably are familiar with the concept of ASM tootes is the nature of a graph or a nature of a function as it reaches a a Untouchable bound as it reaches a very large value it it approaches a certain value right so it's about the nature for ends that are arbitrarily large ends that are very very very large beyond what you could even imagine because when we see how a function behaves on the tail end on the asymptotic end that is when we have a true understanding of its performance because some algorithms might run faster initially we might have a curve running like that and then we might have a line running like that initially the curve is faster or slower but on the tail end is when we see who really wins so enough talking about this let's see an actual definition so first what we need to see is we need to understand the work we're doing so let's define a function it's normally called T of n for the work that our function does okay so we have t of n right there so this is the either the time or the space a function takes as n changes do you see how n is the parameter to the function as we modulate N I can move n n up or I can move n down when I do that the output the output of that function changes and our job is to bound the change in that function bound the possibility of how this function can change as n gets very large so you'll see what I mean we have our function of how things change versus how we modulate n so now what we need to do is establish the definition for Big O and we'll get into the other bounds but let's just look at Big O o which is the upper bound okay so let's look at the rigorous mathematical definition for Big O which is an upper bound it's upper bounding work so let's read this verbatim and see what it means see if it makes any sense T of n is bounded upper bounded by F of n if and only if T of n is less than or equal to some constant c times F ofn the function we chose to bound with for all n greater than the initial n or n not so this this does this make sense to me it really doesn't make sense this is the definition that we get in our introductory classes this is the definition we get when we first learn it and this is this is too thick for me to understand so why don't we break it down and really see what this is suggesting to us so first what this is actually saying to us what it it's proposing is we have a certain amount of work we're doing a certain amount of work given by the function T of n that's our actual graph that's the actual work the algorithm does we want to bound it we want to put a bound over it a cover over it and we'll see what that looks like using a function called f of n so we say t of n can be upper bounded Big O upper bounded by F of N and what are the conditions how do we know that F ofn satisfies how do we know that F of n can upper bound us okay are you still with me so we only can declare this is true if and only if this is true the function that we have if we multiply our bounding function f of n by some constant we will be able to always always always keep T of n under our bounding function so let me show you this is an example and this doesn't need to make sense right now but it will make sense once I do this example so our job is to choose a c so that F of n bounce T of n are actual work so let's let's do a bounding right now so you see exactly what I mean okay so now what we're going to do is we're going to explore bounding we're going to do and try to satisfy what that guy just told us so here's T of n here's our function and what I want to do is I want to choose a class of functions we know our class of functions of how we can bound well we'll become familiar with them over time but we want to bound this somehow so why don't I start start with trying to bound this so let me Define a function that might bound this maybe it might bound it maybe it might not let's try it right now okay so here is our function T of N and I made a random choice I said I want to try to bound with n s so our function we want to try to bound our work with is n^2 so we see n^2 this is the raw function of n^2 multiplied by C being one okay so what we're doing is c times our function is going to be the result of the function we're trying to bound with stay with me this will make sense in a little and now here is the critical critical point am I able to modulate this base function of n^2 so that for all values of a constant I need to find this T of n stays under it so why don't we go crazy why don't we turn C and turn C to 100 and now let me change our graph okay and now is this true if I take all n values on this axis and I go from n KN which might be zero all the way to the end far far far away will T of n always stay below this function and what you see here is it looks like it will this guy's diverging off to here he's going to stay linear and what we see is this is a correct bounding this is an upper found we have satisfied the rules that Big O imposed on us because we found our constant we found a constant C that keeps T of n below the bounding function what is the bounding function the bounding function is n^2 so what can I declare right now so what I can now declare is that this function is upper bounded by n SAR as long as I can choose some multiple C I just proved I can choose a multiple C that will keep this function T of n below me at all times but do do you see a problem with this do you see a problem of choosing n squar i mean this looks like a linear graph we're familiar with linear time don't you think we could improve on our upper bounding so this brings me to my next concept of how tight is our bound how tight is our bound so this is something that is always to be considered when we're trying to bound something we want to be as accurate as possible to not have all this extra wasted space above the function when we're bounding we want to be as tight and exact as possible to what the function is going to do on the tail end so while Big O of n^2 is an upper Bound for this function it is not a tight upper bound it is a loose upper bound and what we need to do is we need to find a tighter uh F ofn to bound this so let's try a different F of n so what we're going to try is a different function we know our function again and we're going to try something faster something to the order of O of N and what we're going to try is we're going to try F of n as the N value and this is what the graph would start out like we'll start C out at one so right now we are searching we are searching for a c value that allows us to keep T of n underneath this function at all times for all n values for all n values so what we need to C is C is one have we achieved or satisfied our constraints we have not satisfied it we see that t of n is still beating this F of N and we have not chosen a correct constant so why don't we go crazy again why don't we choose some crazy constant like a thousand okay that's better we chose a very very large constant and we see that n does satisfy as a good F of n to bound our function obviously this isn't mathematically rigorous I'm just trying to get the idea across but do you see how all it is about is the function in a Big O notation the function in those brackets is a base function that is a base function we choose and after we choose the base function we have to prove we it is a absolute must that we need to be able to find a c that keeps the actual work below c times the base function so it should start coming together now but we chose a crazy C value let's Cho choose a more reasonable one okay so it looks like we're getting Tighter and Tighter to the bounds and I mean we could go and asymptotically get closer and closer to T of n we could keep choosing smaller and smaller C's until we touch T ofn but the the point is proven we've proven that F ofn succeeds as a bound so what we can say is this is a bound to the order of linear time so whenever I say linear time I'm I'm not talking about a specific function I'm talking about a a behavior I'm talking about a behavior of being able to choose a way to bound these functions where C can be modulated we can change C but the base function is our Behavior it defines our Behavior so we can say this okay so we see that this is to the order of linear time we're getting Tighter and Tighter with our upper bound and I hope the definition starts to make sense we choose our base function we find a c value and prove that t ofen stays under it and our bound works that is a valid upper bound whether it is loose or tight we prefer tight bounds though but it's still an upper bound and it satisfies the definition for big O big O is an upper bound so what we need to also see is when do I fail so why don't I get very aggressive again we know our classes of bounding you'll get famili familiar with them again but why don't we be even more vigorous in how we try to bound why don't we bound to logarithmic time and do log n time so let's try that let's choose log n as F of n okay so our our choice here is to use log n as our function f of n that is the function I'm going to try to choose a c value for to keep T of n underneath me because I am bounding over T of N I want T of n underneath me so what I'm going to do is I'm going to try to choose a c value so let's draw the logarithmic function okay so that right there is our function f of n * a constant C we'll say it's one and we see that it does not satisfy our requirements so what we need to do is we need to bump our C value up so let's try to bump C and try to stretch our graph upwards let's try to see if that bounds T of n so why don't we choose a value like 10 okay so we chose another value for C we chose the value of C is 10 so what we see is 10 * log n are we bounding our T ofn now my drawing skills aren't the best but you can see that t ofn eventually beats the function that we're trying to Bound by our bound is snapped it is broken and we see that our C value is bad so why don't we choose an even crazier C value and see what happens why don't we add another zero call it 100 make C 100 okay so you see that there's a race going on here tfn is doing its own thing and our function C * f ofn is doing its own thing our base function has a behavior and I mean these graphs have a shape in themselves and that defines their tail behavior and it's kind of obvious to see that we will never ever ever pick a c value we can never find a c value that is going to bound T of n so watch how what happens when I extend these graphs so that's probably off camera a bit but you see that the T of n is not bounded by this function although we picked a very large constant and we could keep picking values we could pick we could pick a th000 10,000 100,000 if I go to n as a very large value eventually eventually it is not going to bound tfn eventually this function will be beaten by tfn tfn will be slower than it and we cannot declare this as an upper bound we realize that we have failed and log cannot bound this linear function so the reason you can't bound something that runs in linear time to uh log n time you can't upper bound linear time with log n time is because eventually the linear time function is going to be slower than the log end time function we see initially it's faster but at some point we Lo this function loses it can't be an upper bound so log n fails as an upper bound and we see that the best bound we achieved is o of n so a lot of times people ask why do we drop constants why do we drop constants well the reason we drop constants is because the very definition of an asymptotic bound is all about modulating constants to achieve a behavior it's all about a behavior because the the constants are are internal to the very definition of choosing a bound so it would not make sense for me to say Big O of two n Big O of 2 N is not really saying much because we are just saying we're trying to bound some multiple against F of n which would be 2N but there's no point because we could choose any c value so it does not make sense to have constants because it's about Behavior so that that is the critical thing about this that's the main idea I want to get across the whole idea of the behaviors choosing constants and having a tight or having loose bounds um with our functions so this was a Peak at asymptotic bounding with Big O the upper bound so let's look at our other two bounds and then discuss some other bounds shortly so if you understood the previous concept this concept should be simple bigo was about upper bounding functions and think about it in the worst case we care about an upper bound what is the worst I'm going to do well I can upper bound that so for the best case I I care about lower bounds for the best case I care about lower bounds we lower bound with big Omega so big Omega cares about the the lowest amount of work the lowest amount of work we undercut T ofn and we want the lowest amount of work that a function will will do we want to bound that asymptotically so why do we care about this for the best case well the thing is if we have a best case I want to know what is the fastest this can run if I'm looking at a best case I care about the lower bound well we can upper bound it but we it's more interesting to know the fastest it can go which is the least work it can do which is the lower bound which is Big Omega so what we can do here is we can choose an F of n let's try an F ofn like this okay so we immediately see that this works because this function that we're bounding with stays below T of n at all times and we declare this as arbit an arbitrary function just n^2 the T of n is n^2 here and what we see is that this linear function undercuts all the values it lower bounds the work the least work this function do does is going to be linear and is this tight it's it's not as tight as it can be because we can go even tighter like so so what we can do is we can actually bound on the bottom even tighter to n log n here so our function is N2 and the next lower order type of function we could use is n log n and again there's a great resource online called Big O cheat sheet.com which goes through the different orders of of bounding we can use they look like this I'll leave that there they look like that um but this is a little lower than N squared and it's going to give us a tighter lower bounding and that's what big Omega is about a tight lower bound so now that we understand uh Big O and we understand uh Big O omeg GA as our lower bound we can look at Theta which is just Theta because we can have a bigger little we'll see why but just Theta and we're going to look at how that bounds things okay so when we're talking about Theta and bounding to Theta we're talking about a tight bound or an exact bound so this is a combination we're taking our upper bound our lower bound and smooshing them together and that breeds Theta that breeds what this is so if I have this function T of N I need to find a f of n that bouns this from the top and Bounds this from a bottom from the bottom asymptotically so when we combine these two asymptotic bounds it is an exact bound on how this function behaves in in the tail in in its tail Behavior so what we can do is why don't we try a bad function that won't work let's try n^2 okay so we see n^2 is is n s an upper Bound for this well yeah n s is an upper Bound for this but is n s a lower bound we see n s is not a lower Bound for this because it's above the T of n we've automatically lost we automatically lose this is not bounding from the bottom it bounds from the top but it doesn't bound from the bottom so why don't we try something different why don't we try something to the order of linear time this looks linear to me so I need to show that my e n can upper bound this and lower bound this so why don't we choose C for 100 to see if we can upper bound okay so we chose a c of 100 to multiply by F of N and we see we've achieved an upper bound so why don't we multiply uh f ofn for a lower bound why don't we change it so that we can lower bound t ofn Okay so this might not be accurate to scale but what we see is that we were able to choose a c for the upper bound we satisfied Big O's constraint we were able to choose a c for a lower bound we satisfied the constraints for having a big Omega lower bound and now what we did is we proved that F of N is a fit function it is fit to serve as an exact Bound for this function because of our ability to choose the correct C values so what I can say about that function is that we can tightly bound to the linear order of time to the the order of linear time where n is our F of n we were able to choose constants C so that we could upper bound Big O lower bound big Omega and therefore the n f of n equaling N is a function that is able to exactly bound T ofn so those are the bounding that you need to understand you probably won't use Theta you probably won't use big Omega but I just want you to be familiar with them because I mentioned them and I mentioned them in passing situations and I've never taken the time to actually explain myself and and be clear about what is actually meant with each of these bounds so onto something else why do we say Big O why do we say big Omega and there's no big Theta technically because there is no little Theta so I'm going to link an article that's a really good article in the description about why we have Big O and why we have little o why we have big Omega and why we have little Omega but those are things that you're going to very very rarely use but I mean it's just cool to know them so I'm going to link that below and you can look at that if you understood what was talked about here you're going to certainly understand those so that is all for this video I hope this made sense I really wanted to go in depth on explaining asymptotic bounds because it's very important not to just skim over them it's good to know the mathematical definition and then after we know the definition we can just be loose and say this is linear time or this is uh quadratic time and no know that in the back of our minds we actually know what we actually mean that's all for this video If you like this video hit the like button and subscribe to this channel again my goal is to build one of the world's largest or most helpful resources for software engineering interviews we have uh hundreds of topics left and about probably one or two years in this project before I think it's complete to my taste and yeah that's that's basically it [Music]