Asymptotic Bounding 101: Big O, Big Omega, & Theta (Deeply Understanding Asymptotic Analysis)

Okay so for this video today we are going to  have a discussion about asymptotic bounding and   bounding the asymptotic nature of our functions  so I always say things like o of N or N squared   but what do I really mean i I kind of addressed  this in another video where I talked about what   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 asymptoticly 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 ok 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 if the more   we can understand how an algorithm behaves the  better we can optimize it see where its flaws   are see where we can improve things and we can  improve its asymptotic 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 asymptotes 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 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 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 of function takes as  and changes do you see how n is the parameter to   the function as we modulate n I can move and up  or I can move and down when I do that the output   the output of that function changes and our job  is to bound the change in that function bounds   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 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 of n  the function we chose to bound with for all N   greater than the initial n or and 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'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 of  n 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 gonna do is we're gonna   explore bounding we're gonna 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 with trying  to bound this so let me define a function that   might bound this maybe it might bound it maybe  am I 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 squared   so our function we want to try to bound our work  with is N squared so we see N squared this is the   raw function of N squared multiplied by C being  1 ok 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 I to modulate this base function   of N squared 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 a hundred and now let me change our graph   ok and now is this true if I take all n values on  this axis and I go from n naught which might be 0   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 bound 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 squared so what can   i declare right now so what I can now declare is  that this function is upper bounded by N squared   as long as I can choose some multiple C I just  proved I can choose us a multiple C that will   keep this function T of n below me at all times  but do you see a problem with this do you see a   problem of choosing N squared 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 bounce 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 squared 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 f of N 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 functions again and we're gonna try something   faster something to the order of oh of N and what  we're going to try is we're gonna try F of n as   the N value and this is what the graph would start  out like will start C out at 1 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 see is C is 1 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 see 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 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 asymptotic aliy get closer and closer to T  of n we could keep choosing smaller and smaller   C's until we touch T of n but the point is proven  we've proven that F of n 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   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 function  where see can be modulated we can change see 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 of n stays under it and our bound works that is  a valid upper bound whether it is loose or tights   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  x' you'll get familiar familiar with them again   but why don't we be even more vigorous in how we  try to bound why do 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 times a constant C we'll say it's 1 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 ok so we  chose another value for C we chose the value of C   is 10 so what we see is 10 times log n are we  bounding RT of n now my drawing skills aren't   the best but you can see that t2 then 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 a hundred makes see   a hundred okay so you see that there's a race  going on here T of n is doing its own thing and   our function C times F of N 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 bounty of n so watch out 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 a we can pick a thousand ten   thousand a hundred thousand if I go to n as a very  large value eventually eventually it is not going   to bounce T of n eventually this function will  be beaten by T of n T of n will be slower than   it and we cannot declare this as an upper bound  we realize that we have failed and log n cannot   bound this linear function so the reason you  can't bound something that runs in linear time   to 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  n time function we see initially it's faster but   at some point we loop this function loses it can't  be an upper bound so log n fails as an upper bound   and we see that the best boundary 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 internal  to the very definition of choosing a bound so it   would not make sense for me to say Big O of 2n Big  O of 2n is not really saying much because or just   saying we're trying to bound some multiple against  F of n which would be two n but there's no points   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 with   our functions so this was a peek 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  Big O 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 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 of N and  we want the lowest amount of work that a function   will will do we want to bound that asymptotic  ly 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 cannot per bandit but we it's more   interesting to know the fastest sticking go which  is the least work you 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 of n 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 our 'bitch and arbitrary function just   N squared the T of n is N squared here and what  we see is that this linear function under cuts   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 an 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   N squared 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 comm which goes through the different orders   of poundings we can use they look like this I'll  leave that there they look like that 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 O   mega is about a tight lower bound so now that we  understand Big O and we understand big ol mega as   our lower bound we can look at theta which is just  theta because we can't have a bigger little we'll   see why but just theta and we're going to look at  how that balance 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  or lower bound and smooshing them together and   that breathes theta that breeds what this is so  if I have this function T of n I need to find a   f of n that bounds this from the top and bounces  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 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 squared okay so we see  N squared is N squared an upper bound for this   well yeah and squared is an upper bound for  this but is N squared a lower bound we see N   squared is not a lower bound for this because  it's above the T of N and we've automatically   lost we automatically lose this is not bounding  from the bottom it bounced 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 F of n can upper bound   this and lower this so why don't we choose see  for a hundred to see if we can upper bound okay   so we chose a see of a hundred two multiplied by  F of n and we see we've achieved an upper bound so   why don't we multiply F of n for a lower bound why  don't we change it so that we can lower bound T of   n okay so this might not be accurate to scale but  what we see is that we were able to choose AC for   the upper bound we satisfied bigos constraints  we were able to choose AC 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 order of  linear time where n is our F of n we were able to   choose constant C so that we can 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 of n so those are the bounding 's 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 mention  them and I mentioned them in passing situations   and I've never taken the time to actually explain  myself 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 do 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 gonna 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 want you to go in depth on   explaining asymptotic balance 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 quadratic time  and know that in the back of our minds we actually   know what we actually mean that's all for this  video if you liked 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 hundreds of topics lefts and about   probably one or two years in this project before  I think it's complete to my tastes and yeah that's

Channel: Back To Back SWE

Views: 138,133

Rating: 4.9622889 out of 5

Keywords: big O, asymptotic bounds, big omega, big theta, theta, asymptotic analysis, Back To Back SWE, Software Engineering, computer science, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies

Id: 0oDAlMwTrLo

Length: 23min 15sec (1395 seconds)

Published: Thu Feb 28 2019