Big O Notation Deep Dive | The Skill That Gets You Hired

[00:00:00]If you are preparing for interviews at Google, Amazon Meta or any serious tech company, bigo notation is one of the first things you need to understand.

[00:00:08]Every coding interviewer will ask you what's the time and space complexity of your solution. If you can't answer that confidently, it's a red flag. Now, if you're new to coding, bigo might feel confusing like abstract math that doesn't connect a real code. And if you're a senior engineer, you probably learned this years ago. But when someone asks you to analyze a tricky recursive function on the spot, does it feel automatic or do you have to think about it? In this video, we are going to build a clear mental framework. Not just memorizing, but actually understanding how to look at any piece of code and figure out its complexity yourself.

[00:00:44]Let's get started.

[00:00:52]Bigo answers one question. As my input gets bigger, how much slower does my code get? That's it. We are measuring how performance scales. Let me show you why this matters. Say you write a function that finds duplicates in a list. You test it with 100 items, runs instantly, and works perfectly. Your app grows. Now you have 100,000 items.

[00:01:16]Suddenly the same function takes about 30 seconds. Users are waiting. Your app feels broken. What happened? The code didn't change but the input got bigger and the code couldn't handle it. Big tells this in advance before you ship before user complained. If you are an experienced engineer, you have probably debugged this exact situation. A query that was fast for months suddenly get slow because the data grew. Bigo explains why. Now, here is something important. Bigo doesn't give you exact seconds. That depends on your computer, your language, lots of other factors.

[00:01:53]Instead, Bigo gives you shape of growth.

[00:01:56]Does your code stay fast no matter what?

[00:01:59]That's constant time. Does it slow down gradually as input grows? That's linear time. Does it completely fall apart after a certain size? That might be a quadratic or worse. In interviews, after you write your solution, the interviewer will most likely ask, "What's the time complexity? What's the space complexity?" And this happens at every level from new grad to senior positions.

[00:02:23]You are expected to analyze your code.

[00:02:25]So let's make sure you can when we analyze code we count operations not seconds operations. And the operation is something basic comparing two values accessing an array element adding something to the list. Let me show you what I mean. Here is a simple function.

[00:02:43]We are grabbing the first element from a list. How many operations does this take? just one. We go directly to position zero and return it. Here is the key question. Does it matter if the list has 10 elements or 10 million elements?

[00:02:58]No, we are not looking at the other elements. We just grab the first one.

[00:03:04]Still one operation. We call this 01 constant time. The one doesn't literally mean one operation. It means the number of operations stays constant no matter how big the input gets. Now let's look at something different. This function finds the largest number in a list.

[00:03:22]Let's walk through it. We start by assuming the first item is the maximum.

[00:03:27]Then we loop through every item and for each one we check is this bigger than our current maximum. If yes, we update it. How many operations now? If you have 10 items, we check 10 items. If you have thousand items, we got to check thousand items. The work grows directly with the input size. We call this O of N linear time. The n represents however many items we have. Now you might notice in that loop we do a few things per iteration. We compare. We maybe assign a new maximum. So should we call it O2N or O3N? No. Here is why. When your input goes from 1,000 to 1 million, whether you do one thing or three things per item doesn't fundamentally change the picture. What matter is the shape of growth. Linear is linear. We drop the constants. Same idea with multiple terms. O of N² + N becomes just O of N square. When N gets large, the N square part is so much bigger that the extra N barely matters.

[00:04:31]Now let's go through every complexity class you'll encounter. For each one, I'll show you code and walk through exactly how it works.

[00:04:39]O of one means that time stays the same no matter how big the input is. Let's look at two examples here. This graphs an element from a list by its position.

[00:04:50]Whether the list has 10 items or 10 million, Python knows exactly where to look in memory. It doesn't search. It calculates the location directly. And that's of one. Here is another. This lookups a value in a dictionary using a key. Dictionaries in Python use something called hash tables. When you give it a key, it computes where that key should be stored and goes directly there. Again, doesn't matter if you have 100 users or 1 million. The lookup time is the same. Now, 01 operations are often the key to making slow code fast.

[00:05:24]When you need to check if something exist, using a dictionary or set gives you 01 lookup much faster than searching through a list. O of N means if your input doubles your time roughly doubles.

[00:05:38]Let's walk through this. We are searching for a specific value in a list. We start at the beginning and check each item one by one. Is this the target? No. Next one. Is this the target? No. And so on and so forth. We might get lucky and find it early. But in the worst case, if the target isn't there or it's at the very end, we have to check everything. 10 items mean up to 10 checks. 10,000 items mean up to 10,000 checks. That's linear growth. On a graph, it's a straight diagonal line.

[00:06:11]O of N is very common. Probably 35 to 40% of interview problems have O of N as the best possible solution. Anytime you need to look at every element once, finding a maximum, calculating a sum, counting something, that's O of N. O of N² happens when you have a loop inside a loop. Let me explain what this does. We are printing every possible pair of items from the list in this code. The outer loops picks the first item. Then the inner loop goes through all items to pair with it. Then the outer loops moves to the second item. And the inner loop goes through all items again. For each of the n items in the outer loop, we do n operations in the inner loop. 10 items, 100 pairs. 100 items, 10,000 pairs. 1,000 items, 1 million pairs. See how fast this grows? That's quadratic. N * n or n squ. On a graph, this curve shoots up much faster than linear. In fact, in interviews, O of N² often shows up as the obvious first solution to a problem. The interviewer wants to see if you can find something faster.

[00:07:22]O of login is where things get interesting. This is very fast, almost as good as constant time.

[00:07:28]Let me explain the idea first, then show you the code. Imagine you are looking for a name in a phone book, an actual paper phone book with thousands of pages. Would you start at page one and check every name? That would take forever. Instead, you open to the middle, the name you want. Is it before or after you open? Let's say it's after.

[00:07:49]Now, you have eliminated the entire first half of the book. You go to the middle of the remaining half before or after. you elate half again. Each step cuts your problem in half. Now, here's the code and this is called the popular binary search. Let me walk you through this. We track two boundaries, low and high, representing the section of the list we are still searching. We find the middle position. If that's our target, we are done. If our target is bigger than the middle element, we know it must be in the upper half. So, we move our lower boundary up. If our target is smaller, it must be in the lower half.

[00:08:28]So, we move our high boundary down. We keep going until we find the target or the boundaries cross, meaning it's not there. Here is why this is so powerful.

[00:08:38]1,000 items about 10 steps. 1 million items about 20 steps. 1 billion items about 30 steps. A billion items searched in 30 steps. That's the power of logarithmic time. Now important thing to note here is binary search only works on sorted data. If your list isn't sorted, you can't use this trick in interviews.

[00:09:02]Binary search appears in about 15 to 20% of interviews. So it's a pattern to be recognized whenever you can eliminate half of your remaining options at each step. You're probably looking at O of login. Of n login combines linear and logarithmic. This is the complexity of efficient sorting algorithms.

[00:09:22]When you use Python's built-in sorted function or the dot sort method, it runs in O and login type time. The intuition is efficient sorting algorithms like merge sort or quick sort divide the problem into smaller pieces. That division is the login part. At each level, they look at the elements. That's the n part. On a graph, O of N login sits between linear and quadratic. It's efficient enough for most real world applications and about 25 to 30% of interview problems involve sorting as part of the solution. So when you hear find the k largest element or merge these intervals, sorting is usually involved. Now we are entering a dangerous territory or of to power n grows extremely fast. Let me show you an example. A function that generates all possible subsets of a list.

[00:10:16]If the list is empty, there is only one subset, the empty set. So, we return a list containing an empty list.

[00:10:23]Otherwise, we take the first item and set it aside. Then, we recursively find all subsets of the remaining items. Now, here's the key inside. Every subset of the remaining items can either include or exclude the first item. So, we create new subsets by adding the first item to each subset we already have. Finally, we combine both the subsets without the first item and the subsets with it. Now, why is this O of two power n? Think about it. Each item has two choices.

[00:10:55]It's either in a subset or it's not. Two choices per items mean 2 * 2 * 2 n times. And that's two power n. Three items includes eight subsets. 10 items give you 1,024 subsets. 20 items give you over 1 million subsets and 30 items give you over 1 billion. O of two power n appears in about 5% of interviews.

[00:11:19]Usually problems finding all combinations or possibilities. When you see this complexity, interviewers often want to discuss whether dynamic programming could help.

[00:11:29]O of N factorial is the slowest complexity we'll discuss. Factorial means n * nus1 * nus2 and so on and so forth. Here's a function that generates every possible ordering of a list, every permutation. If you have zero or one item, there is only one way to arrange it. We return that. Otherwise, we try each item as the first position. For each choice of first item, we recursively find all orderings of the remaining items and then we combine them. That is the factorial. Now, why is this factorial? For the first position, we have n choices. For the second position, we have n minus one remaining choices. Then n minus2 and so on and so forth. Three items, six orderings, five items, 120 orderings. 10 items, 3.6 million orderings. And 15 items, over 1 trillion orderings. This grows faster than exponential. Now factorial problems are rare in interviews, maybe 2%. The classic example is traveling salesman problem. So when you see factorial complexity you are usually discussing why finding the exact answer doesn't scale.

[00:12:41]Now let me put all of this in one graph from fastest to slowest of one constant dictionary lookups array access by index of login logarithmic such as binary search or halfing problems. O of N is linear single loops through data. O of N log N sorting algorithms. O of N square are quadratic mainly found in nested loops. O of two power N is exponential generating all subsets. O of N factorial. It's generating all orderings. The first four are generally acceptable for production code. The last two are warning size. They usually only work for small inputs.

[00:13:22]Now, let's talk about how to actually figure out big for any code you see. And here's a step-by-step framework you can apply. Step one, identify the input that grows. First question, what's the input that can change size? Sometimes it's obvious, a list with n items. Sometimes there are multiple inputs. A function might take two list, one with n items, one with m items. So, you'll express complexity in terms of both.

[00:13:52]Step two, find the loops. Loops are where work multiplies. This is usually where you start. One loop through n items. That's O of N. Two separate loops one after the other. Still O of N. You add them. O N + O N is equals O of 2N is equals O of N. Nested loops. And this is where you multiply a loop inside another loop through N items, which is O of N².

[00:14:18]Let me show you. One loop will visit each item once of n. Two loops but they are not nested. We do n things and then n more things that's 2 n which simplifies to n. Nested loops for each item of the n items in the outer loop we do n things in the inner loop. n * n= n² that's of n².

[00:14:42]Step three look for halfing. If the problem size gets cut in half each step, that's O of login. Common signs to look for dividing by two in each iteration, binary search pattern or going down one path of a tree. We start with n then nx2 then nx4. How many times can you divide by two before reaching zero? And that's login. Step four, check for hidden operations. This is where people make mistakes. Some operation look simple but have hidden cost. For example, look at this code. See that item in other list.

[00:15:19]Checking if something is in the list requires scanning the whole list. If other list has M items, that's O of M.

[00:15:26]So the total is O of N * M. For each of N items, we do M checks. But if other list wears a set instead, so lookups are O of 1. Now the total is O of N plus O of M is equals O of N plus M. Step five, know your built-in functions. Different operations have different cost. So you better know these. Step six, handle recursion. For recursive functions, think about two things. How many times does a function call itself? How much work does each call do? Multiply them together. And we'll practice this in our next tricky problem section. All right, let's put this framework into practice.

[00:16:10]I'm going to show you problems where people commonly make mistakes and then walk through the correct analysis.

[00:16:16]Tricky problem one, string concatenation in a loop. Here's a code that builds a string from numbers. Let me explain what this does. We start with an empty string. Then for each number from 0 to n minus one, we convert it to a string and add it to our result. The common mistake most people look at this and say one loop O of N. The reality this is actually O of N square. And here is why strings in Python are immutable. They can't be changed. So every time you do result plus string of I, Python doesn't just add to the existing string. It creates a completely new string. So when result has 100 characters and you add one more, Python copies all 100 characters plus the new one into fresh memory. The first iteration copies roughly one character. The second iteration copies roughly two characters.

[00:17:08]The third copies roughly three and so on and so forth. The fix. Instead of building the string piece by piece, we collect all the pieces in a list.

[00:17:18]Appending to the list is O of one. Then at the end, we join them all at once.

[00:17:23]and that's O of N. So total is O of N, not O of N square. The key lesson here is string concatenation in a loop is a classic trap. Use a list and join at the end.

[00:17:36]Tricky problem two. Nested loop that's not always N square.

[00:17:42]Look at this code. People see two loops and immediately say O of N square. Let's actually count. The inner loop doesn't always run n times. When i is zero, the inner loop runs n minus one times. When i is 1, it runs n minus2 times. When i is 2, it runs n minus 3 times. And when i is n minus one, it runs zero times.

[00:18:05]That's approximately n² by 2, which is still of n². So yes, this is of n², but it's important to understand why. It's not just two loops mean n². The inner loop now runs at most 10 times regardless of how big n is. Outer loop n iterations. Inner loop at most 10 iterations. Total n * 10 or o of n. So don't just count loops. Look at what the loop bounds actually depend on. Tricky problem three. Recursive Fibonacci. And this is a classic trap. Here's a simple recursive implementation of Fibonacci in Python. If n is zero or one, we return it directly. That's our base case.

[00:18:47]Otherwise, we recursively add the previous two Fibonacci numbers. But notice this recalculates the same values again and again, which makes it very slow for large N. The common mistake, some people say O of N because N decreases by one or two with each call.

[00:19:04]The reality this is still O of two power N. Let me show you why. To calculate Fibonacci of five, we need Fibonacci of four and Fibonacci of three. To calculate fib of four, we need fib of three and fib of two. To calculate fib of three, we need fib of two and fib of one. Notice something. We are calculating fib of three twice. We are calculating fib of two multiple times.

[00:19:29]If you draw out all the function calls, it forms a tree. And this tree roughly doubles in size for each increase in n.

[00:19:36]Fib of five makes about 15 function calls. Fib of 10 makes about 177 calls.

[00:19:42]Fib of 20 makes about 21,000 calls and fib of 40 makes over 300 million calls and that's exponential growth or of two power n the fix use memorization.

[00:19:56]Now we store each result after we calculate it. So before doing any work we check have we already computed this?

[00:20:03]If yes just return it. Each Fibonacci number gets calculated exactly once and that's of end time. The key lesson here is knife recussion can explode exponentially. So look for repeated work and consider memorization or dynamic programming. Tricky problem number four loop with changing increment.

[00:20:25]What's the complexity of this? The common mistake people see a loop and guess of n. The analysis how many times does this loop actually run? I starts at one then it becomes 2 then four then 8 then 16. You're asking how many times can you double one before you reach or pass N.

[00:20:45]That's the definition of login. This is O login. Now we are starting at N and halfing it each time. Same number of iterations O of login. The key lesson here is doubling or halfing the loop variable each iteration equals O of login not O of N. Problem number five multiple different inputs.

[00:21:08]The common mistake is calling this as O of N square. The correct answer, it depends. If list one has N items and list two has M items, this is O of N * M. You should only call it O of N². If you know both list are the same size. If they could be of different sizes, keep them separate in your answer. Maybe list one always has 10 items and list two has a million. That's very different from both having a million. The key lesson here is when you have different inputs, don't assume they are the same size. Use different variables.

[00:21:45]Now, let me show you how all of these comes together with a real interview problem. This is the classic twosome.

[00:21:51]Probably the most famous interview question. It shows up everywhere. The problem given a list of numbers and a target sum if any two numbers add up to that target. Here the array is 2 7 115 and the target is 22. So the answer is 7 + 15. Now this is how a mediocre candidate solves it. They jump straight into the obvious approach. Check every pair. They explain if I try all combination of two numbers for each number I check it against every other number. If any pair adds up to the target I return true. And this works it gets the right answer. When the interviewer ask about complexity they say nested loops so O of N square time O of one space since I'm not using any extra memory and that is correct and for some problems that might be acceptable but for two sum the interviewer is waiting to see if he can do better and here is how a good candidate solves it.

[00:22:50]A good candidate also starts by thinking about the brute force approach. They might even mention it. The obvious approach is O of N square checking all pairs. But let me see if you can do better. Then they think differently. For each number, I know exactly what I need.

[00:23:04]Target minus that number. Now let me walk you through this solution. We create an empty set called scene. It tracks numbers we have seen already. For each number, we calculate the complement. what we need to add to this number to reach the target. Then we check is that complement in our set. If yes, we found a pair. Return true. If not, we add the current number to our set and continue. And here is our analysis. One loop through n numbers.

[00:23:34]Each set operation is O of one total O of N time. And we are storing numbers in a set. So O of N space in the worst case.

[00:23:44]So with 10,000 numbers, O of N square approach is up to 50 million comparisons. O of N approach about 10,000 operations and that's 5,000 times faster. The mediocre candidate gives a working solution but doesn't push further. The good candidate shows problem-solving thinking. They recognize the brute force approach, identify the inefficiency, and use the right data structure to fix it. And that's the difference between meets expectation and a strong hire.

[00:24:13]So let's recap what we have covered. Big tells you how your code scales. It's the shape of growth, not the exact time. We went through all seven complexity classes from 01 constant time to O factorial. And I walked you through the code for each one so you actually understand what's happening. We built a framework for calculating bigo, identify endpoints, finding the loops, looking for halfing, checking for hidden cost, know your built-in functions, and handle recussions carefully. We worked through tricky problems. string concatenation traps, recussion explosions, and multiple inputs. And we saw how thinking about complexity separates mediocre interview answers from strong ones. For beginners, focus on recognizing the patterns. One loop means O of N. Nested loop means O of N square. Halfing means O of login. That covers most of what you'll see. So take some code you have written or elite code problem you have solved and analyze it using this framework. The more you practice, the more natural it becomes. And if this was helpful, drop me a comment telling which part made things click for you. For more on algorithms, data structures, and system design, check out my courses linked in the description. I'll see you in the next one.