Big-O Notation - For Coding Interviews

hey everyone welcome back and let's write some more neat code today so today I want to run through all the common Big O runtime complexities that you'll need for coding interviews and by the way all of the code from this video will be available for free on neetcode.io if you're not familiar with it it's basically a site that I created it's got a ton of free content to help you prepare for coding interviews including code in Python JavaScript Java and C plus and I've also started making courses so far I completed the data structures and algorithms for beginners course and the advanced algorithms course and I just started uploading the system design for beginners course you can use code neat for 10 off lifetime access that means you'll have lifetime access to all current and future courses so first of all what even is Big O time complexity well it's basically a way of analyzing the run time the amount of time it takes for our algorithm to execute as the input size of our algorithm grows typically we can expect as the input what size of our algorithm grows the execution time of the algorithm is also going to grow but it could grow linearly which you know this is a function you might be familiar with we're used to Y equals X in terms of Big O this is represented as Big O of n where n is just a single variable that's our x-axis now this is where we take a different turn from algebra you could have another function like this which is for example n divided by 2 but we actually don't care about the differences when those differences are constant values we only care about the variable here which is n we don't care about the divided by two and that's true for all Big O run times we also don't care if you know we have n plus some constant like five like that might look something like this on our chart it just starts at a different spot and has the same exact slope but we don't care about these constants either so the first runtime we're going to look at is Big O of one I know we said that we don't care about constants but in this case one is a special constant that we do care about and as you can tell from the chart no matter how much our input size grows the time complexity of Big O of one-time algorithms is always the same you can see it's a flat line because the time it takes for these algorithms does not change based on the input size these are the most efficient algorithms so for example if you have an array of values like this it's a constant time operation to add to the end it's also a constant time operation to remove from the end or just to search an arbitrary index just to look up a value at any index whether it's at 0 or 1 or 2 and the same is true typically for a hash map so to insert any value into a hashmap is constant time to look up a key from a hashmap is also constant time and to remove a key from a hashmap is also a constant time operation and the same operations could be applied to Hash sets as well we also have Big O of n which as we discussed is the linear growth scenario so as our input size grows our time is going to grow proportionately so if we're given some array of values and we want to take the sum of all of those values this sum function is going to be a linear time algorithm because we're going to have to go through every single number in the array so with just three values it won't be too bad but as our input size grows so if our array had a million values in it so then the run time of calculating the sum would also grow and of course we know that's going to happen because under the hood we're going to have to Loop through all of the elements so looping through a list of elements is also a linear time algorithm inserting in the middle of an array and removing from the middle of an array is also Big O of N and that's because when we talk about big of and we mean the worst case run time because in some cases like inserting in the middle well for example inserting in the middle of this array could be over here in in which case we would have to you know put a value let's say we're inserting the value 100 we'd put a hundred over here and then move the 3 into the next position and then this would be our new array so in this case we only had to move a single value but what about if we wanted to insert the 100 over here then we would have to insert the 100 here we'd have to move the one to the right we have to move the 2 to the right and we'd have to move the 3 to the right so that this would be our new array and in this example we had to move every single value in the array we know that's an end time operation so since we don't know where we might insert in the middle we take the worst possible case which would be big of and in this case also removing from the middle is going to be similar if we remove from the end it's a constant time operation but if we move from an arbitrary position for example the first position then we would have to shift every other value to the left and we'd end up with an array that looks like this Now searching an array is also a linear time algorithm in the worst case we would have to look at every single element in the array before we realized that the element in this case if we're looking for a hundred doesn't exist it didn't exist anywhere and we had to look through the entire array to figure that out or we might find the element we might even find it in the first position but we take the worst case which is going to be Big O of n another one that I get a lot of questions about if you have a set of values in this case a list of values one two three and you want to heapify them you want to build a heap out of those elements the heapify algorithm actually runs in Big O of end time if you don't have to individually push an element to a heap it runs more efficiently if you can just build it from scratch this is an end time operation a couple more common algorithms the sliding window algorithm also runs in linear time and I'm actually going to quickly go on neetcode.io over to the sliding Windows section and the second problem in the list when you take a look at the code you see that it does have nested Loops but that doesn't necessarily mean the time complexity is N squared a lot of people assume that just because you have nested Loops the time complexity is N squared but that's not always the case the same is true for the monotonic stack algorithm so once again going on neetcode.io to the stack section the daily temperatures problem is a monotonic stack problem and it also has nested Loops but this algorithm actually runs in Big O of end time if you want more details on these problems I recommend going to neetcode.io you can check out the video explanation and I go more in depth to analyze the time complexity in each of these videos next we have Big O of N squared which we kind of just talked about when you have nested Loops the simplest case is if you actually had a two-dimensional array and you wanted to iterate over that array you would need nested Loops to do that so for example if we had a grid like this three by three so you know it's squared so you know this could be any arbit trade Dimension though n by n you want to First go through every Row in this grid and then for every row you want to go through every single position in the grid so the outer loop is going to go through every single row and the inner loop is going to go through every position in each individual row and what's the size of this grid well it's going to be N squared that's how we get the Big O time complexity for that this is pretty simple another case that kind of trips up some beginners is if you just have a single array and you want to iterate through it n time so if you have an array that looks like this of size n you go through it once that means the Big O time complexity is going to be n if you go through it twice the time complexity is going to be 2 times n which we know reduces to just be Big O of n but what if you iterate through this array n times well then the time complexity is going to be n times n which would be N squared but it's actually not very common that you iterate through the entire array and times what's more common is that you iterate through the entire array once and then you iterate through every element in the array except the first position and then you iterate through every element except the first two positions and you keep doing this until you've just iterate through the last element so this is a diagram of doing that you go through four three two and then one so what would be the time complexity of doing this well mathematically this is actually a well-known series and it can be proven that this will roughly equal N squared divided by two but if you're not smart enough or care about that math portion an easier way to identify that would be well here we have a square right we have an N by n Square now what does this portion of the square look like to you to me it looks like half of a square it basically looks like we cut this in half so now you're probably convinced that iterating through an array like this is going to lead us to N squared divided by 2 time complexity and like I said we don't care about constants so this 2 does not matter therefore we say that iterating through an array like this is also N squared a lot of people kind of brush over this and I'm pretty sure most people never actually learn this or care about it but that's okay because you don't really need to anyway but now you know something that probably most people don't we also talked about how inserting into the middle of an array is an end time operation so insertion sort which basically inserts into the middle of an array n times is going to have N squared time complexity as well another one that's pretty similar to N squared so I won't actually draw this one out on the grid but n times M this could mean a two dimensional Matrix that's not necessarily a square so in our example on the left over here we could have some rectangular array that looks like this where we have two rows and we have three columns so in this case n might be the number of rows where M might be the number of columns we actually have two variables this time which is perfectly valid in Big O notation now if we can have N squared y stop there we can also go up to n cubed and we could actually go higher and higher to n to the power of 4 to the power of 5 etc etc but I won't do that it's pretty uncommon to even have n cubed actually for most problems but this is usually the highest that we get to usually you don't have algorithms that go up to n to the power of four but it's possible and I think you would be able to identify that case if you're able to identify these as well of course we could have some kind of three-dimensional data structure more commonly though you'll just have a single array and you'll want to get every unique triplet from that array for example so in this case we would need three nested Loops to iterate through every single triplet from this input array now let's move on to some of the more complicated ones like log n this is where we get more math involved and I bet you most people don't know how to analyze log n time complexity they kind of just memorize is that because usually log n is applied to binary search for example on an array or you could run binary search on a binary search tree these are the two most common algorithms but there's also pushing and popping from a heap which is another common one on an array the reason binary search runs in log n time is because on every iteration of the loop we eliminate half of the elements from like consideration we don't need to search this half of elements for example so then we'd be left with two elements and we could keep cutting this array basically in half until we have nothing remaining that's when we would have completed our binary search so the question is given an array of size n how many times can you cut the value n by two how many times can you divide it by two until it equals one well another way of talking about this would be how many times can you take the value 1 and multiply it by 2 until it's equal to n AKA 2 to the power of what x in this case is equal to n how do we solve this mathematically well by definition that's what log actually is we take the log of both sides and then we realize that X is equal to log n so therefore the number of times you can take an array like this and divide it by 2 is equal to log n in this case the base of our logarithm is going to be 2. so that's where this comes from and the idea is the same when we're talking about binary search trees at least if your BST is balanced because as we search it we're either going to go to the left or to the right looking for some Target value so if we end up going to the right that means we eliminated the entire left half of the tree from consideration and we do this recursively so we start with a tree of size n and we basically remove half of the elements from consideration until we find the Target that we're looking for that's why this is also a log n time algorithm so log n grows pretty slowly you can't tell from this chart but actually for really really large input sizes log n is practically a flat line like the difference between log n and Big O of n is massive I think log base 2 of 4 billion would be something like 32. so even with an input of billions we get a very small two-digit number now we also have n multiplied by log n and this is actually only marginally less efficient than Big O of n it's a lot more efficient than N squared just like how log n is much more efficient than Big O of n the most common algorithms for n log n are sorting for example merge sort and we usually assume that most built-in sorting functions are n log n so if you need to run the built-in function in a coding interview you can basically assume that it's an N log n algorithm heapsort has the same runtime and this kind of illustrates how we can get a runtime like this we know that popping from a heap is a log end time operation and if we have a heap you know of size n and we have to pop from that Heap while that Heap is non-empty then we end up doing n operations which take log n h therefore we get n log n as the total result now in this example before we started running the heaps or algorithm we actually had to build the Heap so this took Big O of n times so actually the overall run time was n plus n log n should we draw that on our chart well with Big O notation we only care about the larger term if we have a term like this which is strictly larger than this term we don't care about the smaller term but we could have a Time complexity where we have M plus n log n and in this case since m is a different variable from any of the variables we have here we don't know that this is a strictly smaller than this one so we have to include both of these in the Big O time complexity but we don't have that in this case so we reduce the time complexity to just be n log n now let's get into some of the non-polynomial runtimes which starting with the most common is 2 to the power of n and this is the part where I could start going on a nerd tangent and talking about how this equation is actually just a reflection of the log n over you know this axis but I'm pretty sure nobody cares about that so I won't get into it but feel free to comment if you're interested in the math stuff it's most common to have a runtime like this when you're talking about recursion so this is an example of two Branch recursion where our recursive tree will have a height of n but we'll have two branches every time so this is recursively calling some recursive function it's not really doing anything but here you can see we have two branches of recursion visually it would look something like this you know similar to a binary tree but in this case the height of this tree would be measured in terms of n so for example if we were given some input array of size n and we wanted to get all possible combinations that would be one example of 2 to the power of n run time so for example Computing the Fibonacci sequence recursively is a pretty common example or combinations now if we can have 2 to the power of n can't we have 3 to the power of n and what about four to the power of n yeah you can have pretty much any constant let's call it C raised to a power of n now I'm not going to draw those out but with a bigger base value we will have you know increased runtime complexity so an example of that would be pretty similar to our previous recursive example but in this case instead of having two branches we have an arbitrary number of branches so we use a loop to do that so in this case our constant C is going to tell us how many times we need to Loop and make a recursive path so in this case if C was three we'd have a decision tree with three branches and the height of the tree would continue to be n so we would end up with a time complexity of 3 to the power of n now how am I getting that time complexity from a decision tree well think about it this way if we have three uh you know branches on the first level we have three values here now for each of those we're going to have three more branches and then for each of those we're going to have three more branches we're basically going to keep doing this until we reach the entire height of the tree which in this case is n so we're basically going to have a number our base value 3 multiplied by three and just keep multiplying it until we have n of these therefore we get 3 to the power of n now a pretty rare runtime complexity is the square root of n you rarely see this but I still think it's worth mentioning you will rarely ever see this in a coding interview but I think it's still worth mentioning the only example I think I've ever needed this for is getting all the factors of some value so for example if we're given a value n and we want to get all the factors of it we will go through every value between 1 and the square root of N and check if any of those values is a factor of N and since this could possibly produce some duplicate factors we add those factors to a hash set which we know is a constant time operation so the number of times this Loop is going to execute is of course going to be the square root of n now I won't go super in depth on why this algorithm works if you want to know feel free to ask in the comments it's really more of a math problem than a coding problems and lastly we have n factorial which is a math equation which basically means you know if we had 5 factorial that is 5 times 4 times 3 times 2 times 1. so basically it ends up being a very big number we say that this is bigger than 2 to the power of n because 2 to the power of 5 in this case would be two times two times two a five times and you can see that just by looking at these two since factorial has the potential for having larger terms than just some constant value two or three or four that this is going to grow much quicker than this one now n factorial is pretty rare it mainly comes up for permutations and sometimes in graph problems for example the traveling salesman problem but I think you don't have to focus too much on N factorial you mainly have to know that it's very inefficient so if your solution is n factorial most likely you don't have the optimal solution but sometimes n factorial is the best you can do in a real interview I don't think it would matter too much if you can you know precisely tell is your algorithm n factorial or is it exponential to the power of n it wouldn't matter a lot and also knowing the exact difference for example the square root of n is actually growing quicker than log n you could kind of figure that out just by doing some math in your head like I said the log of 4 billion is going to be something like 32 whereas the square root of 4 billion is still going to be a very large number but this is Main only to give you a high level overview of how these time complexities relate to each other because that's what's important you need to be able to know how efficient your algorithm is if you see your algorithm is factorial or exponential or even n cubed you know it's not super efficient you want your algorithms to be on the right side of this chart though sometimes it's not possible if you found this video helpful please like And subscribe it really supports the channel a lot if you're preparing for coding interviews check out neatco.io it has a ton of free resources you can also get 10 off lifetime access using Code neat thanks for watching and hopefully I'll see you pretty soon

Channel: NeetCode

Views: 138,208

Keywords:

Id: BgLTDT03QtU

Length: 20min 37sec (1237 seconds)

Published: Mon Oct 10 2022