Learn Big O Notation In 12 Minutes

in this video i'm going to teach you everything that you need to know about big-o notation so when you walk into your next interview you can nail every single question they ask you about it so let's get started now [Music] welcome back to web dev simplified my name is kyle and my job is to simplify the web for you so you can start building your dream project sooner so that sounds interesting make sure you subscribe to the channel for more videos just like this now to get started instead of diving into exactly what big o notation is i want to present you with an example think about an example where i have three different envelopes and i want to sort these envelopes by where they're going so we have a b and c and obviously a is going to be first then b and then c well there is a ton of different ways that we can sort these letters using code and some of them are going to be quicker than others some are going to take up more space some are going to be better in all regards some are going to be worse in all regards i mean there's literally infinite ways you can sort these letters and as i get more and more letters right now i only have three but what if i have 300 what if i had 3 000 how would these different sorting algorithms that i choose scale would some of them be better as i got more letters maybe they're better when i have less letters and understanding all of these different concepts is incredibly important when you're writing out code and you need to understand what your code is doing and how it's going to perform with the data that you're given all of these different thought considerations around speed and memory usage are what big o notation is built around and the idea of big-o notation is analyzing the algorithm you create for example the sorting algorithm for these letters and figuring out how much space does this take up or how long does this algorithm take as the size of my input changes so as i get more and more letters from 3 to 30 to 300 will my algorithm take up more space or will it become slower and slower and slower and not just will it become slower or will it take up more space but how much slower will it get and how much more space will take up compared to other similar algorithms based on the same sets of inputs so you can imagine that we have these letters and there's a few different ways i can sort them for example i could go through and find the smallest one for example a is going to be first and i could take that and put it into a new list over here then i could go through and i see b down here at the bottom i could put that after a because that's the next one in the list and then i could go in and i could take c and i could slot that in at the very bottom of the list and there we go we have a sorting algorithm and while it's not the quickest algorithm in the world it gets the job done you noticed we took up two different arrays we had a list over here in my right hand and a list in my left hand so we had double the space and we had to loop through our first list over and over and over again which is not that quick so this is just one example of a sorting algorithm which we could classify based on the space and the time that it takes up but it's a little bit difficult looking at these you know abstract examples of envelopes in my hand and trying to turn that into code so let's jump into the code and actually look at some simple examples to figure out how you can analyze them and determine their big o notation so here we are with a really basic example where i have an array right here of data three long and we're just looping through and console logging all of the elements in our array one after another and for our purposes of this algorithm which is this for loop here we want to determine how slow this algorithm is essentially as our input grows so if we go from 3 to 300 inputs how much longer is our algorithm going to take how does it scale as our input scales so generally when you're doing these kinds of determinations the first thing you need to do is figure out what the core part of your algorithm is in our case this core portion is this console.log it is the one thing that our algorithm does over and over and over again to get the end result and then we take this and we determine how many times does this thing happen based on how large our input is so generally what you're going to do is you're going to set some form of variable to be how long your input is this is almost always used as n so you'll see n a lot in big o notation so we'll say the length of our data array is equal to n in our case and now we want to determine how our algorithm grows as n grows and in our case as n goes from 3 to 300 we run this loop three times and then 300 times so it scales one to one with the size of n so we would give this a big o notation of n we'd say big o of n is how this algorithm scales with the size of our input based on time so as our input scales from 3 to 300 our algorithm is going to scale in time linearly essentially it's going to grow one to one with the size of our input if we were to for example do another form of loop we put a loop outside of here we'll say let say j equal zero j is going to be less than data two oops two dot length and then j plus plus and now what we do is we console.log out theta two of j let's just create data two right here and we'll give it you know one more we'll say actually oops data two is gonna be one two three four five so now we have is we have two different loops in our algorithm our algorithm first loops over everything in data two right here and then loops through everything inside the data one so now we have two separate variables we have n which we're going to use for our data one and then data two we need to come up with some other variable we can just say for example b it really doesn't matter we could just even do a and b but in our case we'll have n represent data and b represent the length of data 2. so now our algorithm is going to scale based on the length of data 1 and data 2. so we have a big o here of n plus a because we have data 2 which is a that's the length of data 2 and data 1 which is the length n and we're scaling off of both of those because we loop through everything in data 2 once that's a then we loop through everything in data 1 here n times because that's the length of our array so we have an n plus a length loop here as you can see if we were to modify this slightly though and that we have our loops inside of each other so if we come down here and we want to say for each one of these what we want to do is we want to log data and then we also want to log here data 2 of j so now we're looping through every single element in data 2 and then for each one of those elements we're looping through every single element inside of data 1. so now we have nested loops and now our big o notation here is going to be right here our console log one and we're doing this n times here for every single a time that we go through our loop so this is actually n times a as our big o notation to represent how long this algorithm takes because if we add 1 to our a element here so we go from 5 to 6 now this is going to be looping through our algorithm one more time for each element inside of our data here because we have these nested loops inside of each other and generally when you start seeing nested loops like this you're going to run into pretty poor performing algorithms and your big o notation is going to scale quite quickly for example if we just simplify this and make this data here get rid of data 2 completely we're just going to print out date of i and data of j just like this that would be essentially n squared over here for our big o notation and that's because every single time we loop through n we have to loop through n again for each element of n and when you start to see these types of algorithms this is when you start to run into problems because these perform very slowly as your input grows for example with an input size of 3 we perform this console log 9 times but if we just bump this up to five now we have to perform that 25 times so it's growing exponentially and you'll see it just skyrocket off if your input is 100 long you're going to have to perform this inner part tons and tons of times and it's going to really slow down your algorithm now what if we take this and instead of having this one console log we do this four times for example you you'd think this would go to four n squared but when you're doing big o notation one thing that you almost always are going to do is remove any leading constants like this so this 4 we don't really care that it's 4n squared because the 4 is kind of meaningless it's just based on the size of the input here what we really care about is this n squared here this is really going to tell us how the algorithm grows over time so we can just completely remove any leading constants like this or if we even had like a plus two here because we logged out before things started twice we can remove that as well because we only really care about how it grows over time based on our input so any extra constants or any extra added numbers like that we can just completely remove and again speaking of extra added sections let's say we took another loop and added it down here where we lived through each one of our elements again we just printed them out like this so now we have our console log here and our console log here so this is n squared plus n because we're looping through n squared times here and n times here but when you see this kind of scenario we just cut off all of the things that scale less so n squared scales way quicker than n because 4n squared is going to be 16 and obviously 4 for n is just 4 and as n grows in size n squared is going to grow way quicker than n so we just delete the n we don't care about the things that scale less quickly now for the most part we've only been looking at time-based big-o notation but another way you can look at big o notation is based on space complexity so how does your algorithm grow in memory usage as the input size scales so let's just delete all this that we have up here and let's just be left with this basic for loop that we started with and you can see that our space complexity for this is essentially zero we're not adding any extra space because we're not creating anything inside of this so you would call that essentially a big o of one because it's going to be constant the space does not change as our input size scales because we're not actually creating anything inside of this but what happens if we were to create a brand new array let's say we come out here const out is going to be equal to an array and inside of here we're just saying out is going to be equal to data of i we want this to be out of i there we go so now what we're doing is we're creating a brand new array essentially from the values inside of our data array and this is going to be a space complexity of n because our output is going to be the exact same length as our input here they're both going to be a length of three and the amount of memory that this algorithm takes up is exactly the same amount as the input size of our element but if we were to go even a step further and let's say we created another for loop inside of here based on j we'll do j plus plus and here we created a brand new array so we have out oops out of i is going to be equal to a new array and then the out of i of j is going to be equal to this data of i in our case actually j data of yeah data of i so what this is going to do is it's going to output to us three new arrays inside of our output and the first array is going to be the letter a repeated three times b repeated three times and then c repeated three times and this is going to have a space complexity of n squared and that's because we have this output which is going to be three times the size of our input because our input is three and if we have an input size of four this output is going to be 16 elements large because it's going to have four arrays with four elements in each of those four arrays and that's going to continually scale larger and larger and larger as our input grows and it's going to be that squared level of n squared here generally though when you're dealing with big o notation you're almost always going to be worried about the time complexity of the algorithm so worrying about space is not something you're going to see very often but it's important to know how to analyze these algorithms to determine how much space they are going to take up but like i said time based is going to be where you're going to use big o notation the most and that's all there is to big-o notation if you enjoyed this video make sure to check out my other videos linked over here and subscribe to the channel for more videos just like this thank you very much for watching and have a good day

Channel: Web Dev Simplified

Views: 58,808

Rating: 4.9382873 out of 5

Keywords: webdevsimplified, big o notation, big o, big o notation algorithm, big o notation js, big o notation tutorial, big o tutorial, big o notation exaplained, big o examples, big o notation java, big o notation python, big o notation javascript, big o notation algorithms, big o algorithmss, big o guide, big o notation guide, big o programming, big o time complexity, big o complexity, big o space complexity, big o time, big o space, big o notation complexity, big o of n, js, wds

Id: itn09C2ZB9Y

Length: 12min 18sec (738 seconds)

Published: Sat Aug 15 2020