Big-O Notation - Everything you Need for Coding Interviews

Big O notation is a pretty big deal and not just when it comes to coding interviews. When you write a piece of code, you want to have a rough idea of how efficient it's going to be. Sometimes it doesn't matter when the input size is small. But as the input size grows, the execution time of your algorithm is also going to grow. And you want to know how quickly. And that's where big O notation comes in. Now, it is a little bit mathematical. I'm not going to lie. Ben, suppose you're on a game show and you are given a chance to choose from three different doors. — But I'm going to show you it's really not so bad. I'm going to use a lot of pictures, diagrams, and examples. Let's start with the simple equation y = 5x + 2. The coefficient 5 determines the slope. The constant + 2 determines the initial y intercept. But in big O, we only care about how quickly the algorithm is going to grow as the input gets very large. for this equation. That means that we actually don't care about the constant plus 2. And we also don't care about the slope 5. The only thing we care about is that it grows linearly. And that's because if we have a different function x2, we know that x^2 is going to pass any linear equation regardless of the slope. Now, there's a little bit of calculus behind this that I won't get into, but also keep in mind that actually the rate of growth doesn't always tell the whole story, even though that's what Big O is about. The input size does matter, and we are going to discuss that a bit. But before that, I wanted to quickly tell you guys about today's sponsor, Warp. Warp is a really powerful tool which interfaces as a terminal, but has all the capabilities of state-of-the-art AI tools. It has two modes, terminal mode and agent mode, but I usually just leave it in auto, which means it auto detects what I'm typing and then switches into the appropriate mode for the uh prompt or command. So, for example, I can write in natural language that count the number of lines of code in the current directory. So, it's an auto mode. Let's see what it does. And it looks like it came up with a pretty elaborate command that I would not have known off the top of my head. 130,000 lines of code. And with the recent 2. 0 release, there's so much more that I can do now. So, I'm going to ask it to add another button to my navbar on Neat Code. io. And I'm going to call it jobs. And pretty quickly, you can see it already has the first change. So, it looks like it's importing the icon for that on the navbar. And this interface is really, really nice because not only can you accept or reject these changes, but you can actually go inside and you can actually edit the changes. If you're working on a DSA problem, you can even ask Warp to help you debug your code, help you fix compile errors, even analyze the runtime complexity of your code. I personally believe that in the long run, AI agents will assist developers rather than replacing them entirely. And Warp is a tool that is designed with that philosophy. There's a lot you can do to configure it to your liking. You can set rules so that Warp remembers your preferences. There's MCP support. You can run multiple agents in parallel. You can install it for free at warp. dev and use the link in the description for Warp Pro, which gives you more AI credits. Now back to the video. Let's start with constant time complexity. Constant time means that the algorithm does not grow with respect to the size of the input. So it doesn't matter whether the input is big or small. The total number of operations is always going to remain the same. A good example of this would be with the hashmap data structure. Hashmaps have an amoratized time complexity that is constant for each operation. insert, delete, lookup, doesn't matter. And that's because these operations are implemented with a hash function. Doesn't matter how big the hashmap is, an operation is always going to take the same amount of time. Unless, of course, we are going to rehash the hashmap, which is something we're not going to cover. And that's kind of why I say amoritized time complexity, which basically means over a large amount of operations, the average time is going to be pretty efficient. It's going to be constant. If you want to learn more about that, you can check out the DSA for beginners course on Necode. io. I teach it kind of the same way. Video explanations, animations, written writeup, as well as some suggested problems for each lesson. Now, constant time doesn't always mean fast. In some cases, a constant time operation might be slower than one that is a linear time operation. For example, allocating a linked list node on heap memory is probably going to be more inefficient than reading through a array if it's a relatively small one. So do keep in mind that big O doesn't always tell the whole story when it comes to realworld

execution time. Logarithmic time complexity is an interesting case. As the size of our input doubles, for example, from 8 all the way to 16, the number of operations will only increase by one. Typically when we talk about log we mean log base 2. An example would be log base 2 of 8. By definition it means what power would we have to raise two so that it would equal 8. In this case it's three. If you double it log base 2 of 16. What power do you raise two to? Well to the power of four and then you get 16. So you kind of see what I mean. Another way to look at it would be how many times do you take a number like 16 and divide it by two such that it equals 1. This definition allows us to understand the classical example of binary search. Of course, binary search works by cutting our search space in half at each step. So if you start with an array of size 8, how many times can you cut it in half? About three times. So that's why we say that the time complexity of binary search is log base 2 n. Beyond binary search, logarithmic complexity appears whenever we divide our problem in half at each step. Database indexes, binary search trees that are balanced and even divide and conquer style algorithms like merge sort. Linear time obviously means that the execution time grows linearly with respect to the input. But keep in mind that this doesn't always mean that the slope of that line is one. It could be greater than that. Perhaps when our input size is five, the total number of operations is 10. And perhaps when we double the input size to 10, then the total number of operations is also going to double in this case to 20. Linear search is a good example. Suppose we're given an input array that is not sorted. Thus, we can't run binary search on it, forcing us to run a linear search. In the worst case, we'd have to consider each element in the input. So, this is an example of a linear time algorithm. Another more interesting example would be the sliding window algorithm, which often times is implemented with nested loops. But don't let this fool you. Nested loops don't always imply an nsquare runtime, which we will cover in just a bit. But in this case, we have two loops. The outer loop will run n times and the inner loop will also run a total of n times. Visually, you can think of it as having two pointers. You don't necessarily know when the second pointer is actually going to be shifted. That pointer is controlled by the inner loop. But you do know that both pointers will only visit each element a single time. So in some sense, you could consider this a linear time algorithm with a slope of two. each element in the input is going to be visited at most two times. So indeed it is a linear time algorithm. Next up we have n log n which is more inefficient than linear time because while log n grows very slowly compared to n, it does still grow. Some quick math would be when we have an input size of 8, we have 24 operations, 8 * 3. When we have an input size of 16, we have 64 operations. 16 * 4. You can see that the n factor is growing quickly, but the login factor is growing pretty slowly, but still growing. Merge sort is a really great example. We have two steps in this algorithm. The split step, which will divide our array in half into two equal halves. So, we'll have a total of log n levels cuz that's how many times we can split the array. But at each level we will end up looking at every single element reading it and possibly swapping it with its neighbor. Meaning at each level we will have n total comparisons done. When you multiply these two terms together you get n log n. Interestingly for comparisonbased sorting algorithms n log n is actually the theoretical limit that we can achieve. When dealing with multiple inputs of different sizes we often see the n * m complexity. So these are just two variables that are different. Common example is a rectangular grid where the number of rows and columns differ. So for example, a 3x5 grid, the total number of elements in that is going to be 3 multiplied by 5, which is 15. So reading a grid like this is going to depend on not just one dimension, but both dimensions of the grid. But another example of this time complexity could be having two different arrays and we have nested loops to possibly compare every single pair of values in both arrays. N^ squ means the time complexity is going to grow quadratically which is much less efficient than linear time or even n login time. It's actually a bigger

difference than you would think. For example, when n is five, we might have 25 operations. When n is 10, we might have 100. When n is 100, we might have 10,000 operations. The classic example is nested loops where both iterate through the same input. For each element in the outer loop, we process the elements again in the inner loop. But again, keep in mind that not all nested loops are going to be n squared. In this example, you can see that the inner loop is actually not incremented by one. It's doubled each time, making it a log n loop. Triple nested loops would be n cubed. and we could kind of keep going from there. The big jump happens when you get to exponential time complexity which is where things get really slow. Exponential is kind of like the inverted cousin of log n. It means that every time you increment the input size the total number of operations is going to roughly double. You can even take integers for example. We know that typically integers are stored with 32 bits. This gives us a range of two billion positive numbers. But if you have 64bit integers, well, you didn't just double the amount of integers you could have. You doubled it 32 times. So, you know, take roughly 2 billion and square it. That's kind of why 64-bit architectures are, you know, mostly satisfactory at this point. We don't really need to go beyond that. In most cases, recursive Fibonacci calculation is actually a perfect example. For each number we make two more recursive calls. So our branching factor is two which is the base of our time complexity. And the power of the time complexity is going to be proportional to the height of this recursive tree which is roughly going to be n where we want to calculate the nth Fibonacci number. This is why we try to avoid exponential algorithms whenever possible or use techniques like dynamic programming to cache repeated values. Factorial time complexity is the nightmare scenario. But sometimes it is unavoidable in algorithm design. As n grows, the operations grow very quickly. For n= 3, we have six operations. For n= 5, we have 120. For n= 10, we have over 3 million. If it's not obvious to you why n factorial grows more quickly than 2 to the power of n, think of it like this. When you have the example n= 10, 2 ^ of 10 is 2 multiplied by itself 10 times. So you have 2 * 2 and you have 10 terms. Well, 10 factorial also has 10 different terms being multiplied by each other except the terms are just larger. They're growing linearly. So you have 1 * 2 * 3 * 4 etc. Other than the one, all of the rest of the terms are larger. You can see why as n grows more and more that this is going to grow much more quickly than even exponential time. This commonly appears when we're generating all possible arrangements or permutations. For each additional element, you multiply the number of possible arrangements by that number. The traveling salesman problem is another classic example. Finding the shortest route through n cities requires checking n factorial different possible paths. Now, with all that said, I want to reiterate that big O really doesn't tell you the whole story. For example, iterative solutions are typically preferred over recursive solutions. And that's not just because your interviewer is being a jerk and wants you to write up the dynamic programming bottomup solution. It's also because of hardware. Recursive solutions use stack memory. Each consecutive recursive call is pushed onto the stack space which is often limited. Now sometimes running a program you can increase the stack limit but in general it's more limited than heap memory which is why iterative solutions are often preferred. If you enjoyed this video and you want to see more animations like these along with practice problems, definitely check out necode. io. There's plenty of free resources on there as well as a few indepth courses to teach you algorithms and data structures and also do it interactively with practice problems, in-depth solutions, and a few interactive courses to learn Python specifically for coding interviews. All the tips and tricks that you would ever need. The things that took me hundreds of hours to learn, I tried to distill into a few pretty concise courses.