What Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Notation.

Key Takeaways

okay so what we're gonna discuss today is asymptotic bounding it's very important for algorithms and this is generally something that if you don't have a sound fundamental understanding of you're going to be mistaken in an interview you're going to say a complexity that's completely wrong again if you have not subscribed to the channel subscribe to a channel like this video so when we see a single four loop doesn't that mean linear time when we see two for loops doesn't that mean quadratic time right not always so I think what we have to look at first is a little math and a little calculus I was never amazing at calculus but to really understand asymptotic behavior we need to look at what asymptotic really means so what is asymptotic behavior really mean so I have a graph here so what is this graph so maybe I don't know the equation for this graph but I can tell about where this graph is going so if I took the limit as X approaches infinity if I go towards infinity where does the Y value go and you see that the Y value goes towards zero so this is what this looks like okay so now we see the asymptotic behavior of the graph of 1 over X which is what this graph is this is the graph of 1 over X the asymptotic behavior of it is that as X approaches infinity we get closer and closer to 0 and you notice our points of interest what we're interested in here is tail behavior the idea of asymptotic sand looking at an asymptotic behavior is we want to see how does the graph behave getting into very very large X values into very large values this is the idea of asymptotic complexity ok so now we know what asymptotic means it means tail behavior but wait why don't I just measure the elapsed to real time why don't I just take the wall time why don't I just do that why don't I just do what I see in Li code I mean I run my code on LI code and it tells me this ran in this many milliseconds so I guess I know how strong my algorithm is right so that is not the best way to approach things so in computer science often problems are applied at a grand scale like if you're writing an algorithm for a company like Facebook or a large company it's going to be used across millions and millions of users and large inputs to an algorithm so our best point of interest is to see how does this behave on the tail end how does this behave as input gets very large we only see the true measure of performance of an algorithm when we have very very large input and this is why asymptotic complexity intrigues us in computer science so let's look at an example to really drill this in so we have an algorithm insertion sort that is going to do two times N squared comparisons so this could be any random implementation and for some reason it does two times N squared comparisons so we have a merge sort implementation that does 50 times n log n comparisons so we know that insertion sort is slower and don't worry about the constants here they're just arbitrarily chosen so we have computer a running the slower algorithm insertion sort but computer a runs at ten billion instructions per second and we have computer be running the faster algorithm but computer B is 1,000 times slower than computer a it is 1,000 times slower but it's running a faster algorithm so what is the approximate wall time going to be for both of these computers computer a and computer B okay so can you guess them now now do we have an idea of which is going to be faster okay so we see that the actual running time for the faster computer is going to take 5.5 hours and is running a slower algorithm and we see that computer B is a thousand times slower it is a thousand times slower but it's going to only take 20 minutes to run so why was this algorithm faster and why was this algorithm slower why did the slower algorithm lose on a computer is a thousand times faster so the answer to that question lies in the idea of asymptotic bounding and looking at the asymptotic behavior so I think something to really drill in this concept is looking at linear time looking at the class of poundings that we call linear time so whenever I say linear time I say this in a lot of videos I say we're going to have a linear time bound what does that actually mean so I want us to look at a few different graphs so what we're going to do is I'm going to draw a few graphs and we're going to notice something in common between them and is going to lead us to the most critical word in all of that we're doing so let me start drawing graphs so here is our first graph y equals 1 over 2x okay so we have one graph so let's draw another graph ok so here is another graph we see that this is the graph of y equals x so let's draw two more graphs just to really hammer this point home ok so I just drew the graph y equals 2x and I just drew the graph y equals 3x so what do you notice about these graphs I want you to mentally imagine this if i zoom out when our input is super super super large when i zoom far outwards what are all of these going to do what will they all look like do you see how all of these are lines do you see how all of these are lines all of them have these same tail behavior all of these graphs have the same behavior so the key thing behind asymptotic complexity is the whole point of taking asymptotic measures is so that we know how a graph is behaving when input is very large when input is very large that is when we see a graphs true colors so do you see why we drop constants if I have a Big O of 1/2 of n so why do I drop the 1/2 why does it just become Big O of n why is Big O of N and asymptotic measure so you see this is the exact area because all of these graphs will do the same thing when we get very very large input they will scale in a linear fashion this is a linear scaling when I say log n time when I say linear time when I say quadratic time when I say cubic time when I say factorial time when I say exponential time what am I saying I'm not describing a individual graph I am describing a class of functions I'm describing a class of behaviors and that is what this is all about okay and that is all for this video if you like this video like if this video was clear if this made things a little clearer about why we use Big O notation why we do asymptotic complexities LIKE the video and subscribe to the channel I think every one of these videos is a tiny building block to build a larger picture to make you very competent and able in the interview that is the key to this we're just slowly building that knowledge set until you are in a very strong level along with your Lea code studying to do well in the interview so that's what this is all about so awkward [Music]