How to Calculate Time Complexity of an Algorithm | Loops & Recursion

The interviewer looks at your code, and asks one question. "What's the time complexity?" And most people freeze. They guess. "O of n?" "Maybe n squared?" And in an interview, a guess is a red flag.

Today, that ends. By the end of this video, you'll have a step-by-step method to calculate the time and space complexity of any code. Loops, nested loops, while loops, and recursion. No guessing. No memorising. Just counting.

Welcome back to Compiled Canvas. This is Episode Three of our DSA series. In Episode Two, we learned what Big O means, and how to spot it quickly. Today, we go one level deeper: how to calculate it, and prove it, step by step.

Here's the plan. A five-step method that works on any code. Simple statements, if-else, and code in sequence. Every kind of loop: linear, logarithmic, and square root. Nested loops, including the tricky ones where the inner loop depends on the outer one. While loops and two pointers, and why some loops that look like n squared are actually linear. Recursion, with the recursion tree method, and the five recurrences you need to know. The hidden costs inside library calls. Space complexity, step by step. Three full worked examples. A trick to know the complexity you need, just from the problem's constraints. How to say your answer in an interview. And a quiz at the end. So grab a pen and paper, and calculate along with me.

Let's go.

First, a thirty-second recap. Big O describes how the work grows as the input size, n, grows. We care about the worst case. We drop constants, so two n becomes n. And we drop smaller terms, so n squared plus n becomes n squared.

Now, the method. Five steps, and it works on any code.

Step one: find the input size. What is n? The length of the array? The length of a string? The number itself? And if there are two inputs, like two different arrays, give them two names: n and m.

Step two: find the work that repeats. Loops and recursive calls are where the time goes. A single line outside a loop barely matters.

Step three: count how many times it repeats, in terms of n. This is the real work, and it's what most of this video is about.

Step four: combine the pieces. Code that runs one after another, you add. Code that's nested inside other code, you multiply.

Step five: simplify. Keep the biggest term, drop the constants, and that's your Big O.

Add for sequence, multiply for nesting. Remember that, and you're already halfway there.

Let's start with the building blocks.

A simple statement is O of one. Assigning a variable, doing arithmetic, comparing two numbers, reading an array element by its index. It takes the same time, no matter how big the input is.

Ten simple statements in a row? Still O of one. Ten is a constant, and constants disappear.

Now, if-else. Say the if branch runs a loop over the whole array, and the else branch just returns a value. Which one counts? In the worst case, we assume the more expensive branch runs. So this if-else is O of n. Always take the worse branch.

And code in sequence. Suppose your method first runs a loop over the array. That's O of n. Then it runs a nested loop. That's O of n squared. One after the other, so we add: n plus n squared. Then we simplify. The smaller term disappears, and the answer is O of n squared. In sequence, the slowest part wins.

Now, loops. For any loop, ask two questions. How many times does it run? And how much work happens inside, each time? Then multiply. Iterations, times the work per iteration.

Loop one. For i from zero to n, i plus plus, with simple work inside. It runs n times, and each time is O of one. That's O of n.

Loop two. The same loop, but i goes up by two each time. Now it runs n over two times. But one half is a constant, so it's still O of n. Going up by two, by three, or by ten: any constant step is still linear.

Loop three. A loop that runs from zero to one hundred, no matter what n is. That's a hundred steps, every time. A constant. So it's O of one. If the loop's limit doesn't depend on n, the loop is constant.

Loop four. i starts at one, and doubles every time: i times equals two. One, two, four, eight, sixteen, all the way up to n. How many steps is that? The number of times you can double one before you reach n. That's log base two of n. So this loop is O of log n.

The same is true when i starts at n, and halves every time. You can only halve n about log n times before you reach one. Doubling or halving means log n. And multiplying by three, or by ten, instead of two? Still log n. In Big O, the base of the log doesn't matter.

Loop five. i starts at one, and the loop runs while i times i is at most n. So i stops at the square root of n. This loop is O of square root of n. You'll see it in prime checking. To test if a number is prime, you only need to try divisors up to its square root.

Now, nested loops. This is where interviews are won and lost.

The simple case first. An outer loop runs n times, and inside it, an inner loop runs n times. For each of the n outer steps, you do n inner steps. So we multiply: n times n. That's O of n squared. Three loops nested, each up to n? n times n times n. O of n cubed.

But careful. If the outer loop goes over an array of size n, and the inner loop goes over a different array of size m, the answer is O of n times m. Not n squared. Two different inputs get two different letters. This is a very common mistake, and interviewers notice it.

Now, the tricky one. The inner loop depends on the outer one. The outer loop: i from zero to n. The inner loop: j from i plus one to n. This is how you compare every pair exactly once.

So how many steps? When i is zero, the inner loop runs about n times. When i is one, n minus one times. Then n minus two, and so on, all the way down to one. Add them all up. n, plus n minus one, plus n minus two, down to one. That sum is n times n plus one, over two. Roughly n squared over two. Drop the half, and it's still O of n squared.

Here's a picture that helps. Draw an n by n grid. The full grid is n squared. The dependent loop only fills half of it: a triangle. But half of n squared is still n squared.

Next. An outer loop that runs n times, and an inner loop that doubles, j times equals two, up to n. The inner loop is log n. So the total is n times log n. O of n log n.

And now, a classic trap. The outer loop halves: i starts at n, and divides by two each time. The inner loop runs from zero to i. Most people say: the outer loop is log n, the inner loop is n, so the answer is n log n. Wrong!

Count the real work. The first time, the inner loop runs n times. Then n over two. Then n over four. Then n over eight. n, plus n over two, plus n over four, and so on. That adds up to less than two n. So the whole thing is O of n. Linear!

The lesson: when the inner loop's limit keeps changing, don't just multiply. Add up the actual work.

While loops follow the same rules. Ask: what changes on each step, and when does it stop?

Take two pointers. Left starts at the beginning, and right starts at the end. On every step, either left moves forward, or right moves back. Once they meet, the loop stops. So there are at most n steps in total. That's O of n.

Now, here's one that fools almost everyone: the sliding window. An outer loop moves the right pointer across the array. And inside it, a while loop moves the left pointer forward, to shrink the window. A loop inside a loop, so it must be n squared, right?

No. Look at what the left pointer does. It only ever moves forward, and it can never go past the end. So across the whole run, the inner while loop moves at most n times in total. Not n times per outer step: n times overall. The right pointer moves n times, and the left pointer moves n times. n plus n. That's O of n.

This is called amortized analysis. Don't count how many times the inner loop could run on one step. Count how many times it can run in total. Every element enters the window once, and leaves the window once. That's linear.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now, recursion. For recursive code, there's one formula. The total time is the number of calls, times the work done in each call.

And to count the calls, draw a recursion tree. Each call is a box. The calls it makes are its children.

Example one: factorial. Factorial of n calls factorial of n minus one, which calls factorial of n minus two, all the way down to one. The tree is a straight line, with n calls. Each call does O of one work, a single multiplication. So the time is O of n.

Example two: recursive binary search. Each call looks at the middle, and makes one call on half the array. n, then n over two, then n over four. About log n calls, each doing O of one work. So it's O of log n.

Example three: simple Fibonacci. Fib of n calls fib of n minus one, and fib of n minus two. Two calls per call. Draw the tree. One call at the top. Then two. Then four. Then eight. The number of calls roughly doubles at every level, and there are about n levels. That's about two to the n calls. So it's O of two to the n. The exact growth is closer to one point six to the n, but in an interview, O of two to the n is the answer they expect.

And here's the magic. Store each answer the first time you compute it. That's called memoization. Now, each Fibonacci value is computed only once. n different values, with O of one work each. Fibonacci drops from O of two to the n, to O of n. That's the big idea behind dynamic programming, which we'll cover later in this series.

Example four: merge sort. It splits the array in half, sorts each half recursively, and then merges the two halves in linear time. Draw the tree. At the top, one call working on n elements. On the next level, two calls on n over two each. Still n in total. Next, four calls on n over four. Still n. Every level does n work. And how many levels are there? You keep halving, so there are log n levels. n work, times log n levels. O of n log n.

That's the recursion tree in one sentence: work per level, times the number of levels.

You'll often see the time of recursive code written as a recurrence. T of n means the time for an input of size n. Here are the five you need to know. Pause and screenshot this.

One. T of n equals T of n minus one, plus constant work. One smaller call, and constant work. That's O of n. Like factorial.

Two. T of n equals T of n over two, plus constant work. One call on half the input. That's O of log n. Like binary search.

Three. T of n equals two T of n over two, plus n. Two calls on the halves, plus linear work to combine them. That's O of n log n. Like merge sort.

Four. T of n equals two T of n minus one, plus constant work. Two calls that only shrink by one. That's O of two to the n. Like simple Fibonacci.

Five. T of n equals T of n minus one, plus n. One smaller call, but linear work every time. n, plus n minus one, plus n minus two, and so on. That's O of n squared. Like a recursive selection sort.

For harder recurrences, there's a formula called the Master Theorem. You won't need it in most interviews. If you can draw the recursion tree, you can solve almost anything.

One line of code is not always O of one. Library methods can hide a loop inside. So when you count, count these too.

Arrays dot sort, and Collections dot sort: O of n log n. Contains, indexOf, or remove on an ArrayList: O of n, because they scan the list. Adding to the end of an ArrayList: O of one, on average. Removing from the front of an ArrayList: O of n, because everything shifts left. HashMap and HashSet get, put and contains: O of one, on average. TreeMap and TreeSet operations: O of log n. Substring, and joining two strings with plus: O of the length of the string. And copying an array: O of n.

So a loop over n items, that calls contains on an ArrayList inside? That's n times n. O of n squared. Swap the ArrayList for a HashSet, and it becomes O of n.

Now, space. Space complexity measures the extra memory your code needs, as the input grows. Usually, we don't count the input itself. We count what you add on top. That's called auxiliary space.

Use the same method, and look for three things.

One: new data structures. A new array of size n, a HashMap that can hold n entries, a list you build up. Each one is O of n space. A two-dimensional n by n grid is O of n squared.

Two: a fixed number of variables. A few counters and pointers are O of one space, however big the input gets.

Three: the recursion stack. Every call that hasn't finished yet is waiting on the call stack, and takes memory. So the space of recursion is the maximum depth of the recursion tree. Not the total number of calls.

That's an important difference. Simple Fibonacci makes about two to the n calls, but its deepest path is only n calls long. So its time is O of two to the n, but its space is only O of n. Recursive binary search goes log n deep, so it uses O of log n space, while the loop version uses O of one. And merge sort uses O of n extra space, for the temporary arrays it merges into.

Let's put it all together, with three full examples. Try each one yourself first.

Example one. Find if any two numbers in an array add up to a target. The code sorts the array first, and then uses two pointers, one from each end. Step by step. The sort is O of n log n. The two-pointer loop is O of n. They run one after the other, so we add: n log n, plus n. Keep the bigger term. The time is O of n log n. And the space? Just two pointers, so O of one extra, apart from the sort itself.

Example two. Count all the primes up to n. For each number i from two to n, try every divisor from two up to the square root of i. The outer loop runs n times. The inner loop runs up to the square root of i, which is at most the square root of n. Nested, so we multiply: n times the square root of n. The time is O of n root n, and the space is O of one. In Episode Five, we'll make this much faster, with the Sieve of Eratosthenes.

Example three. Generate all the subsets of an array with n elements. Each element is either in, or out. Two choices, n times. So there are two to the n subsets. And copying each subset into the answer takes up to n work. The time is O of n times two to the n. The answer itself holds all those subsets, so the output takes O of n times two to the n space, while the recursion only goes n deep.

Here's a trick that top competitive programmers use every day. You can often tell the complexity you need, just from the problem's constraints.

A computer does roughly ten to the eight, a hundred million, simple operations per second. And most judges give you about one second. So:

If n is up to about ten, even O of n factorial can pass. Up to about twenty, O of two to the n is fine. Up to about five hundred, O of n cubed. Up to about five thousand, O of n squared. Up to about a million, you need O of n log n. Up to about a hundred million, only O of n. And beyond that, you need O of log n, or O of one. Think binary search, or a math formula.

So when you see n up to ten to the five, you know instantly: n squared would be ten to the ten steps. Far too slow. You need n log n or better. That one line in the problem tells you which approach to look for, before you write a single line of code.

And in an interview, don't just say a letter. Say it like this.

"The time complexity is O of n log n, because the sort dominates. The two-pointer pass after it is only linear. And the extra space is O of one."

Name the complexity. Say which part dominates. And mention the space, too. That one sentence tells the interviewer you really understand your code, and it earns points even when your solution isn't the best one.

Okay, quiz time. Three snippets. Pause the video, work out the time complexity, and then hit play.

Question one. The outer loop starts i at one, and doubles it, up to n. Inside, the inner loop runs j from zero to n.

Question two. A loop over an array of size n. Then, after it, a separate loop over a second array, of size m.

Question three. A recursive function that does constant work, and then calls itself twice, each time on n over two.

Ready?

Question one: O of n log n. The outer loop doubles, so it runs log n times. And each time, the inner loop does n work. Log n, times n.

Question two: O of n plus m. Two separate loops, one after the other, over two different inputs. So we add them. And we keep both letters, because we don't know which one is bigger.

Question three: O of n. This one's sneaky. Two calls, each on half the input. The tree has one call, then two, then four, all the way down to about n calls at the bottom. One, plus two, plus four, up to n, adds up to about two n. Each call does only constant work, so there's no n per level. It's linear, not n log n.

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

Let's recap. Find n. Find what repeats. Count it. Add for sequence, and multiply for nesting. Then simplify. A constant step is linear. Doubling or halving is log n. A square root limit gives root n. For dependent loops, add up the real work. Don't just multiply. For amortized loops, count the total moves, not the moves per step. For recursion, it's the number of calls, times the work per call. Or, the work per level, times the number of levels. Space is the extra memory, plus the recursion depth. And the constraints tell you the complexity you need.

Your homework. Pick five problems you've already solved. For each one, write the time and space complexity, line by line, with the five steps. Then check your answer against the official solution. Post your trickiest one in the comments, and I'll check it.

Next episode, we set up our toolkit: Java basics for DSA. Arrays, strings, wrapper classes, and the collections you'll use in every single problem, with the complexity of every method you call.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.