Complete Beginner's Guide to Big O Notation

everyone it's cold I'm back from my not so short break I was supposed to be like a week it turned into two weeks life got in the way I moved my studio is sort of set up it's like the only thing currently unpacked but it's good enough so I have a video here on big o-notation this is a very important topic I get asked about it a lot I use JavaScript as the language for some of the code snippets in this video but there's nothing really JavaScript specific about this topic in other news I have a new video coming out most likely next week on webpack something I get asked about a lot something I see in the comments and the polls oh and I'm very excited to say that I'm almost done with my react course a very big react course it won't be on YouTube but there will be lots of react content on my youtube channel in the next few weeks and months I'll have more information about the course as I finish editing and launch it so you'll know and while I have you here please subscribe to the channel turn on notifications comment share with everyone and your family your friends your school your church your job your world I do spend most nights just compulsively refreshing my youtube channel seeing if my subscribers go up or down I like to go up and down it's the only way I derive my self-worth so please like and subscribe alright I'm just kidding but it does make a big difference enough of the chitchat let's get on to the notorious b.i.g o notation Big O notation so where's a good place to start well imagine that we have multiple implementations of the same function ten different variations they all work and they're all different how do we know which one is best here's a more concrete example write a function that accepts a string and returns a reversed copy of that string there are many many approaches to doing this in doing some googling here's a Stack Overflow post I found with 10 unique implementations all different so I'm not talking about you know switching out a four loop for a while loop changing variable names these are completely different approaches how do we compare these how do we know which one is best what does best even mean it would be nice if we had a little scale a chart on the wall when I'm teaching that I could point to and say you scored green for greats you scored orange for that sort of thing but we don't quite have that but it's kind of what Big O notation is going to help us do it's going to help us talk about our code and compare our code so why should you care well it's important to have a good vocabulary to talk about how your code performs especially when you're talking about trade-offs between different approaches and you're trying to make decisions about which road to go down also if you have an understanding of what makes your code perform well what speeds things up which makes it slow it will also help you a lot when you're trying to debug things you'll be able to find bottlenecks and pain points finally and this is probably one a lot of you who are watching this care about big o-notation comes up a lot in interviews it's not my favorite topic personally but that doesn't stop a million people from asking it all the time alright let's look at some simple code two functions that calculate the sum of all numbers from 1 up to and including some number n so here's our first one it uses a loop we loop n times and we have a total variable starts at 0 each time through we add whatever our loop number is to that total so it starts at 0 then we add one two three four all the way up until we hit N and we return total the second version is shorter a lot shorter and it uses some magic mathematical formula I had a slide on how you derive this and I ended up removing it just to keep this video nice and brief but trust me this works we take n whatever it is let's say it's three we're going to multiply 3 times 4 which is 12 divided by 2 that gives us 6 the same answer we get over here 3 plus 2 plus 1 is 6 ok so they both work you can trust me how do we know which one is better well it's sort of complicated because what does better mean is it the faster algorithm whichever one finishes first is it the one that takes up less space less memory on our machine is it one that's more readable is it one that is shorter the number of lines does that matter for this video we're gonna be focusing on speed what we'll call time complexity I'll touch a little bit on space complexity at the end but we're really focusing on speed so it seems like a good place to start would be using timers we could simply grab the current time performance now and then call add up to and then grab the current time after it finishes immediately after and then subtract the two and we should be able to tell how long it took and then we could try that on the other version and compare them however it doesn't really work that well the problem with time sounds like a title of an album an aging rocker would come out with at the end of their career but really there are some problems with timing our code first is that different machines will record different times second the same machine will sometimes record different times I'm going to show you this in just a moment also sometimes your algorithms are so fast that testing them with a timer is not going to be precise enough so here's a nice little tool some of my friends at a boot camp called rhythm school made that's not an ad I promise so this tool allows you to select one of those methods so here is our first add up to that uses the loop and here's the second one we're talking about with the magical mathematical formula and what we can do is pass in a number n and it will time it and plot how much time it takes on a chart so let's start simple let's plot one and then what about when we pass two three four five whoa what happened to five why did it go down six why is this getting slower as we go and then coming back up it just doesn't make a lot of sense it seems highly unpredictable and that's mainly because this is happening so quickly our JavaScript timer is just not precise enough in addition if I try 10 again so 10 was apparently very quick the first time if I try it again this time it was like a lot faster one more time it keeps moving up wow that was way faster so my point here is that it's highly unpredictable and now if we add in our second version let's see if it's any better so I'm going to speed through this plot two and three okay so I fast forwarded just a bit I plotted all the first ten numbers on this other one add up to second you can see it's just as unpredictable it's up and down it's hot and cold it's yes and no it's changing all the time and it doesn't really give us a good idea of which one it's better however we can get a much better idea if we zoom way out and we make our numbers way way larger so let's go back to the first one and test 100 and then 1000 and then 10,000 and let's just keep adding zeroes I will warn you if you play with this tool and you start using really large numbers on some of these other examples your browsers are not going to have a good time so just be careful you can see it's starting to take a lot longer and I'm going to stop here because the next one will take a couple of seconds at least now let's go to our second version with the fancy math and do the same thing so we're really just looking at a much further zoomed out much bigger picture view to try and get an idea of how they perform and this is not at all practical to actually test your code this way but I don't know if you can see the gray down at the bottom it's way way way down there and at this point we can see there's a clear trend this gray one is way faster overall when we zoomed in to the first couple of digits it was really unpredictable up and down it didn't make a lot of sense we couldn't really decide which was better but now that we're way in doubt we can tell definitively this one is much faster overall as we make n way bigger as we approach infinity and that's the approach we're going to take in evaluating our code we're going to think about how it performs as it gets towards infinity as the input n grows to an insane and sane level but of course we're not going to make a graph and chart our code every single time we want to understand how it performs relative to other code so instead of working with time what we're going to do is work with the number of operations we'll be able to determine how something performs just by looking at it without actually having to run the code without having to print a graph or a chart we'll be able to look at it and roughly approximate what that chart will look like if we were to plot it so we count the number of operations with a very simplified way of counting as you'll see in a moment so our first or the second example excuse me the simpler one that was much better on the chart only has a couple of operations one multiplication one addition one division and it doesn't matter how large n is if n is a million or if n is five we have the same number of additions multiplications and divisions it doesn't change so we would say three simple operations regardless of the size of n if we compare that to this example as engross we have a loop and this loop is dependent on the value of n so we have n additions inside of that loop if N is a million were adding a million times we have n assignments we have n additions and assignments up here in the loop we have one assignment at the beginning it doesn't really matter what the exact number is we're looking at big-picture trends but you can see that as n grows towards some large large number approaching infinity this number of operations we're going to have to do is going to grow at least in proportion with n so on the last slide the number of operations was somewhere between 2 n + 5 n + 2 if you were trying to be exact but it doesn't matter because as we've already discussed it's just about what that big picture graph looks like and as n increases the number of operations we have to do is going to increase roughly in proportion with n so now it's time to officially introduce the definition of Big O Big O notation is a fuzzy way of formalized counting so we say fuzzy because we're not being very specific we're just zooming way out and we're imagining what the number of operations looks like what that chart looks like as n gets way larger and it's just a nice way of describing sort of pointing to that chart that I showed you at the beginning saying this is good this is mediocre this is F this is terrible except instead of saying you know green for good and orange for meth instead we actually describe it with a mathematical function so here's the actual definition we say that an algorithm is o of a function f of n if the number of simple operations the computer has to do is eventually less than a constant times f of n the function as n increases what this is really saying is that there's some function it could be a linear function of n it could be a quadratic function N squared it could be a constant function of just one whatever this function is when we say something an algorithm has o of n or oh of N squared all of that function we mean that as n grows the amount of operations the time it takes is going to grow roughly in proportion with this function and I should mention there are many other options this can be pretty much anything but there are some common things you'll see like the ones I've listed and all over them at the end okay so let's talk about this example the add up to n we saw that there was three operations no matter what the size of n is but remember we want fuzzy counting we just want the big picture so we would call this o of 1 what this means is that as n grows if n is 10 if n is a million if n is a trillion trillion whatever comes after a trillion it doesn't matter the number of operations we have to do stays the same and if we were to plot that on a chart it would look like a completely flat line there is no increase in the amount of time it takes the number of operations as we move towards a larger n now if we compare that with this one add up to n where we have a loop based off of n we know that the number of operations is going to grow in proportion with n some multiple of n it doesn't matter if it's 10 n 1 n or 50,000 n it doesn't matter we just want the general trend so as n grows larger so does the number of operations so this is called linear time where the line looks something like this a sort of diagonal line not sort of a diagonal line where as n grows over here the number of operations it takes to calculate the result is also going to grow in proportion versus our first one we saw which is constant time is always the same roughly we saw the reality of it it was not exactly the same it was different every time but when we look at the trend the function we would use to describe this chart this this line is f of n so here's another example count up and down it takes number n and it prints all of the numbers from 0 until N and then it does the opposite going down so it goes from n down to 0 and it prints all the numbers in this case we have two loops the first one is going to be o of n the second one is o of n so you might think we would say this has a time complexity of oh of 2 n but we only care about the big picture and we simplify it down to o of n it doesn't matter once again if it's 2 n or a thousand n it doesn't matter in the grand scheme of things because as n grows towards infinity this coefficient in front whether it's 10 or a million is so small and significant we just describe it as event finally another example a little bit different we have a nested loop never a good thing to see if you're trying to write fast code so we have print all pairs which is just going to print all the pairs of numbers between 0 and n like 0 1 0 2 0 3 and then 1 2 1 anyway we have our first loop that runs n times and each time through that loop we have another loop that runs n times so this means for every end that we put in we're going to have to run N squared operations roughly so when you have an O of n inside of an O of n when you have a nested loop we're talking about o of N squared which is called quadratic time and if you can think back to like I guess algebra is when we learned that trigonometry or something very very steep line is what o of N squared looks like so I'm going to refresh the page here and I'm gonna start by printing all pairs this is the one that just showed you that had oh of N squared and let's try doing 10 and then 50 you got to be very careful with this one because N squared grows very very quickly so so far it looks like it's linear but as I start adding larger ends you can see what's happening let's go up to maybe 250 you see how much time it's taking already 280 I don't even want to go to 300 my computer is not going to be happy okay so if we look at this chart it doesn't look that steep but now let's also add in our first example add up to first which was oh of n this is linear time so as n grows the number of operation grows roughly in proportion with n so let's try 10 and then we'll try 20 and now let's try 50 okay how about 100 1000 10,000 take a look at how much faster this is compared to N squared N squared is this one up here that looks almost like a straight line at this point N squared is going to grow extremely fast so here's a chart that shows some of the most common Big O functions some of the bit most common time complexities so this first one down here is constant time o of one that's great if you can write a function that takes the same number of operations no matter what n is and it works then you should absolutely use it but most of the time we can't sometimes you can but it's often very difficult so this one here o of log n we haven't talked about logs in this video but log N and another one called n log n come up often when we're dealing with more advanced data structures like trees and sorting algorithms so I'm not gonna go into it here but I just want to show you what it looks like it's good as well if you can have a time complexity of log n it's almost ideal here is linear time o of n so as n grows to 50 the number of operations roughly grows to 50 as well we get that a nice 45-degree angle line then we have n log n again this comes up in more advanced data structures and sorting algorithms and then our worst nightmare quadratic time N squared this is going to grow extremely quickly and you want to avoid writing algorithms as much as you can that have a time complexity of N squared it's not good there are some helpful rules that you can keep in mind when you're trying to determine the time complexity of an algorithm so first one is that constants don't matter o of 2n it's just o of n over 500 that's just how of one o of 13 N squared that's just oh of N squared remember that these numbers are inconsequential when n is getting massively huge massively huge and is skyrocketing 500 doesn't mean much compared to 1 especially if N is a million or trillion trillion trillion even though that's not a real number similarly smaller terms don't matter o of n plus 10 that's just of n o of 1000 n plus 50 just o of n o of n squared plus 5n plus 8 getting tricky here it's only o of N squared smaller terms don't matter and 5n is way way smaller than N squared if you ever have any doubt in your mind try plugging in a very large number for N and just compare the difference between N squared and then 5 times n the general trend is just oh of N squared there are a few more rule or short hands you can keep in mind when you're trying to determine time complexity I am going to breeze through them pretty quickly it is just a short YouTube video the first is that arithmetic operations are constant time so if you're adding something or subtracting something you can assume or multiplying or dividing it doesn't matter what n is if N is a thousand if N is a million or if n is five just assume it takes the same amount of time same thing with variable assignment also the same thing with accessing elements in an array or in an object it's constant time that's the way those objects work they give you very quick lookup same thing with arrays now in a loop the complexity is the length of the loop times the complexity of whatever happens inside of that loop so if a loop happens n times we're gonna call it o event but if there's something nested inside of it that happens n times then all of a sudden we're talking about N squared as we've seen all right pop quiz here a couple examples I'd like for you to try and think about how this function works as n grows what's that line going to look like on a chart what are we talking about here remember fuzzy big picture counting zoom away out this one is called log at least five so you pass a number in n and all that it does is it loops at least five times and more if n is larger than five so we take the max of five and n so if n is ten we'll be looping ten times if N is a thousand we loop a thousand times but if n is two we're gonna loop five times so how would we simplify the Big O what is the answer it's just o of n it doesn't matter that we are looping five times when N is 1 when n is two when n is 3 because that's so inconsequential compared to the grand giant scheme of things alright pop quiz part two log at most 5 how does this one work it's going to take the minimum of 5 and n so if n is 10 we're going to loop five times if N is a thousand we loop five times if n is two then we're going to loop two times so how would we describe the Big O of this function o of one it's constant time we loop end times if n is less than five but after we hit five if n is six seven eight all the way up to a million anything higher than that we're going to be looping five times every time but we don't say o of five remember we just simplified down ho of one constant time this will generally take this exact same number of operations no matter how large n is so this has been a very quick introduction I have a whole course on algorithms and I spend probably ten videos just talking about Big O notation time complexity something called space complexity which I'll touch on in a moment but I just want to recap what this shows us here these are some of the most common functions in Big O notation but it's not limited to these here but as we write code and we think about how it performs as n grows to some insanely huge number if we can extract that and assign it a general fuzzy value like okay this one is going to be o of 1 and this other solution we have is oh of n we can tell that this one is always going to be or almost always going to be faster this is the better algorithm if we're talking about time complexity compared to an algorithm that has linear time for example an especially quadratic time so I'll touch on space complexity briefly it's the same idea except we're focusing rather than on the run time rather than the number of operations we're talking about the size the amount of memory we have to allocate as n grows and that's all I'm gonna do here on space complexity it's the same idea we think about and growing to a massive number towards infinity and we tried to assign it a function that describes how the amount of space the amount of memory that it uses is going to grow alrighty thanks for watching everyone I hope that made some sense I know it's a lot to cram into a single video if you enjoyed it please like the video subscribe do all of that I really appreciate it and next week I should have a video out on webpack so you can look forward to that if you care about it and that's it for me

Channel: Colt Steele

Views: 175,159

Rating: 4.9512515 out of 5

Keywords: BigO, CS, JavaScript, Algorithms

Id: kS_gr2_-ws8

Length: 21min 58sec (1318 seconds)

Published: Thu Feb 07 2019