Big O Notation Explained Simply | Time and Space Complexity in DSA

Two programs. Same problem. Same correct answer. One finishes before you can blink. The other takes almost two minutes. And in a coding interview, that second one fails, even though it's right.

The difference has nothing to do with your laptop, or your programming language. It's called time complexity. And by the end of this video, you'll be able to look at almost any piece of code and tell how fast it is, in seconds.

Welcome back to Compiled Canvas. This is Episode Two of our DSA series. In Episode One, we built the complete roadmap. Today, we start phase one, with the single most important idea in all of DSA: Big O.

Here's the plan. Why we don't measure code in seconds. What Big O actually means. The seven complexities you'll see again and again, each with real Java code. Four rules to simplify any Big O. A ten-second method to spot the Big O of any code. Space complexity, and the trade-off between time and memory. Best, average and worst case. The hidden traps that fool most beginners. And at the end, a quick quiz. So stay with me, and try to answer before I do.

Let's go.

First question. Why not just time the code with a stopwatch?

Because the same code runs at different speeds on different machines. A gaming laptop, an old phone, an online judge on a busy server. Even the same machine gives you a different time on every run. Seconds tell you about the computer, not about the code.

So instead, we count steps. How many basic operations does the code do? And more importantly, how does that number grow as the input grows?

That's what Big O is. Big O describes how the work grows when the input size, which we call n, gets bigger. It doesn't care whether one step takes a nanosecond or a microsecond. It cares about the shape of the growth.

Picture a graph. Along the bottom, the input size. Going up, the number of steps. Some lines stay flat. Some climb slowly. Some shoot up like a rocket. Big O is simply the name of that line.

And by default, Big O talks about the worst case: the maximum work your code could ever need for an input of size n. Because in an interview, and in production, the worst case is what breaks things.

Now, the seven complexities you need to know, from fastest to slowest.

Number one: O of one, constant time. The work doesn't depend on the input at all. Reading an element from an array by its index. Getting a value from a HashMap by its key. Whether the array has ten items or ten million, it's one step.

Number two: O of log n, logarithmic time. Every step cuts the problem in half. The classic example is binary search. Look at the middle of a sorted array. If your target is bigger, throw away the left half. If it's smaller, throw away the right half. Repeat. A million items? About twenty steps. A billion? About thirty. That's the power of halving.

Number three: O of n, linear time. You touch every element once, like adding up all the numbers in an array with a single loop. Double the input, and you double the work.

Number four: O of n log n. This is the speed of good sorting, like merge sort, or Java's own sort methods. It's a little slower than linear, but much faster than what comes next. Whenever a solution says "sort first", you're probably at n log n.

Number five: O of n squared, quadratic time. A loop inside a loop. For every element, you check every other element, like comparing every pair to find a duplicate. Ten thousand items? A hundred million steps. This is where most brute-force solutions live.

Number six: O of two to the n, exponential time. Every step branches into two. The famous example is the simple recursive Fibonacci, where each call makes two more calls. Add just one to n, and the work almost doubles. At n equals fifty, that's tens of billions of calls.

Number seven: O of n factorial. Trying every possible ordering, like generating every permutation of a list. Just twenty items have over two billion billion orderings. This is as slow as it gets.

Pause and screenshot this ladder. O of one, log n, n, n log n, n squared, two to the n, and n factorial. Every algorithm you learn in this series will land somewhere on it.

Now, four rules to simplify any Big O.

Rule one: drop the constants. If your code loops through the array twice, that's two n steps. But Big O only cares about the shape, and two n grows the same way as n. So two n is just O of n.

Rule two: drop the smaller terms. If your code has a nested loop, and then a single loop, that's n squared plus n. When n is a million, n squared is a trillion, and the extra million barely matters. So it's O of n squared. Keep only the biggest term.

Rule three: steps in a row add, steps inside each other multiply. A loop, then another loop, is n plus n, which is O of n. A loop inside a loop is n times n, which is O of n squared.

Rule four: different inputs, different letters. If you loop over one array of size a, and then another array of size b, that's O of a plus b, not O of n. And if one loops inside the other, it's O of a times b. Mixing these up is one of the most common interview mistakes.

And one bonus fact. In Big O, the base of the logarithm doesn't matter. Log base two and log base ten only differ by a constant. So we just write log n.

So how do you spot the Big O of any code, in ten seconds? Ask four questions.

One: find the loops. How does the loop variable change? If it goes up by one, that loop is O of n. If it doubles, or halves, that loop is O of log n.

Two: are the loops nested, or one after another? Nested loops multiply. Loops in a row add, and you keep the biggest.

Three: is there recursion? Count how many times the function calls itself, and how deep it goes. One call that goes n deep is O of n. Two calls that go n deep is O of two to the n. And if each call halves the input, think log n.

Four: check the hidden costs. Sorting is n log n. HashMap get and put are O of one. Contains on a list, substring, and copying an array are all O of n. Count them like loops.

Loops, nesting, recursion, and hidden costs. Four questions, and you can read the speed of almost any code.

Time isn't the only thing that grows. Memory does too. That's space complexity: how much extra memory your code needs as the input grows.

A few counters and variables? O of one space. A new array the same size as the input? O of n. A two-dimensional grid of n by n? O of n squared.

And here's the one that surprises people: recursion uses memory too. Every function call waits on the call stack until it returns. So a recursive function that goes n calls deep uses O of n space, even if it never creates a single array.

Now, the big idea. Very often, you can trade memory for speed. Take the classic Two Sum problem: find two numbers in an array that add up to a target.

The brute-force way checks every pair with two nested loops. That's O of n squared time, but only O of one extra space.

The smart way walks through the array once, and stores each number in a HashMap. For every new number, it asks the map: have I already seen the number I need? That's O of n time, and O of n space.

On a hundred thousand numbers, that's the difference between almost two minutes and a few milliseconds. Remember the two programs from the start of this video? This is them. We spent a little memory, and saved a lot of time. That trade-off is the heart of so many interview solutions.

Next, best, average and worst case.

Take linear search: looking for a value in an unsorted array. If it's the very first element, you're done in one step. That's the best case. If it's the last one, or not there at all, you check all n. That's the worst case. On average, about half. But we still say linear search is O of n, because Big O plans for the worst.

Quick sort is a famous example where the cases differ. On average, it's O of n log n. But if it keeps picking a bad pivot, it slows down to O of n squared. Interviewers love asking about that.

Now, the traps. These are hidden costs that make code slower than it looks.

Trap one: string concatenation in a loop. In Java, strings can't change, so every plus creates a brand new string, and copies everything so far. Do that n times, and a loop that looks linear is actually O of n squared. Use a StringBuilder instead.

Trap two: methods that hide a loop. Calling contains on an ArrayList scans the whole list, so it's O of n. Put that inside a loop, and you've got O of n squared, without ever writing a second loop. The same goes for indexOf, remove, and substring.

Trap three: adding to an ArrayList. Sometimes Java has to grow the array and copy everything, which costs O of n. But that happens so rarely that, averaged over many adds, each add is still O of one. That's called amortized constant time.

And here's the rule that ties it all together, from Episode One. A computer does roughly a hundred million simple steps per second, and most judges give you about one second. So look at the input size. If n is around a hundred thousand, n squared is ten billion steps. Way too slow. You need n log n or better. The constraints in the problem are secretly telling you which complexity they expect.

Okay, quiz time. Three snippets. Pause the video, work out the Big O, and write your answers in the comments.

Question one. A loop where i starts at one, and doubles every time, until it reaches n. What's the complexity?

Question two. A loop from zero to n, and inside it, a second loop from zero to one hundred. What's the complexity?

Question three. A function that calls itself twice, each time with n minus one, and stops when n is zero. What's the complexity?

Ready? Here are the answers.

Question one: O of log n. Doubling reaches n in log n steps, just like halving in binary search.

Question two: O of n. The inner loop always runs exactly one hundred times. That's a constant, and constants drop. One hundred n is just O of n.

Question three: O of two to the n. Every call branches into two, so the calls double at every level.

How many did you get right? Tell me in the comments: three out of three, two, or one. Be honest.

Let's recap. We measure code in steps, not seconds. Big O describes how those steps grow as the input grows, in the worst case. Know the ladder: one, log n, n, n log n, n squared, two to the n, and n factorial. Drop the constants, drop the smaller terms, add steps in a row, multiply the nested ones, and use different letters for different inputs. Space complexity counts extra memory, including the call stack. And you can often trade memory for speed.

Your homework. Take three problems you've already solved, and write the time and space complexity next to each one. Then check your answer against the best solution.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Like the video, so it reaches more students. And hit the bell, so you catch the next episode the moment it drops.

Next episode, we go one level deeper: how to calculate the complexity of any code. Loops, nested loops and recursion, step by step, so no interview question can catch you off guard.

Keep coding, stay consistent, and I'll see you in the next one.