Analysing loops and recursion

Why this matters

You now know the common growth rates. The next skill is the one you use every day: given real code, decide which rate it has. For code built from loops, the method is to count how many times the innermost statement runs. For recursive code, the method is to write down how the cost of a call relates to the cost of the smaller calls it makes.

Both methods are mechanical once you have seen the patterns. This lesson walks through each pattern with a program you can run, so you can compare your count with the machine's count. By the end you should be able to take a function you have never seen and produce a defensible complexity in a couple of minutes, which is exactly what an interviewer asks.

The core method for loops

One idea covers every loop: count how many times the innermost statement runs, as a function of n. Everything else is bookkeeping.

For a single loop, the count is the number of passes. For nested loops, you add up, over every pass of the outer loop, the number of passes of the inner loop. When the inner loop's count does not depend on the outer loop's variable, that sum is a multiplication. When it does depend, you need a small sum.

A tool helps. The function below runs a piece of loop code and counts the body executions, so we can check every analysis in this lesson against reality. We will write each loop as a small function that returns its counter.

1 1 1 2
10 10 4 20
100 100 34 200

single runs n times. step_by_three runs about n / 3 times: for n = 100 the values of i are 0, 3, 6, ..., 99, which is 34 values. A step of three divides the count by three, and dividing by a constant is dropped by Big-O, so this loop is still O(n). two_in_a_row adds two loops, n + n = 2n: O(n).

The lesson from this table: changing the step size by a constant factor, or repeating a loop a fixed number of times, never changes the class. Changing how the counter moves in a different way, such as multiplying it, does.

Pattern 1: independent nested loops

When the inner loop's length does not depend on the outer loop's variable, multiply.

20
100
1000000
3000

The count is n * m. If both are n, the class is O(n^2). If the inner count is a fixed 3, the class is O(n). Note how the last line has 1,000 outer passes but only 3,000 total steps: the second variable matters.

Pattern 2: the dependent loop, or the triangle

Often the inner loop runs up to the outer variable, so its length changes with each outer pass.

1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
10 45 45
100 4950 4950

The columns are n, the loop count and the formula n(n-1)/2, and the last two agree on every row. For n = 6 the loop runs 0 + 1 + 2 + 3 + 4 + 5 = 15 times.

That sum has a standard closed form, which you should memorise:

1 + 2 + 3 + ... + k = k(k + 1) / 2

You can derive it in your head. Write the numbers forward and backward, then add column by column: every column sums to k + 1, and there are k columns, so twice the total is k(k + 1). Halve it. The story is that a young boy was asked to add 1 to 100 and saw that 1 + 100, 2 + 99, 3 + 98 all make 101, with 50 such pairs.

For the triangle loop the sum runs from 0 to n - 1, so the total is (n - 1) * n / 2. That is n^2 / 2 - n / 2. Drop the n / 2, drop the 1/2: O(n^2). The picture shows both the full square and the triangle.

A six by six grid for a full double loop and a triangle for a loop bounded by the outer counter

A triangle does half the work of the square, and half is a constant. This is why shrinking an inner loop by starting j at i + 1 is a worthwhile speedup in practice but not a change of class.

Pattern 3: the loop that halves

When the counter is divided or multiplied by a constant each pass, the loop runs a logarithmic number of times.

2 1 1
8 3 3
100 6 7
1000 9 10
1000000 19 20

Both functions give about log2(n). Halving from 1,000 reaches 1 in 9 steps (1000, 500, 250, 125, 62, 31, 15, 7, 3, 1). Doubling from 1 passes 1,000 in 10 steps (1, 2, 4, ..., 1024). The cause is the same in both: the remaining work shrinks, or the reached value grows, by a factor of two per pass.

A value halved from 32 down to 1 in six passes

What if the factor is 3 or 10? The base of the logarithm changes, but base changes are a constant factor: log3(n) = log2(n) / log2(3). Still O(log n).

A subtle case: the counter that grows by a growing step. What about i += i? That is the same as i *= 2: logarithmic. And i = i * i? Squaring each time takes a number from 2 to 4, 16, 256, 65,536 in four steps: a loop that squares its counter runs about log2(log2(n)) times, tiny. Such loops are rare, so mention it only if the problem has one.

Pattern 4: a log loop inside a linear loop

Put a halving loop inside a loop over n and you get n times log n.

8 24
64 384
1024 10240

For n = 1,024 the inner loop runs 10 times for each of the 1,024 outer passes: 10,240, which is n log2 n. This shape appears in algorithms that do a binary search for each item, or that walk a tree for each element.

Pattern 5: a loop inside a halving loop

Reverse the nesting and the answer changes in a way that surprises people. Here the outer loop halves and the inner loop does work that depends on the outer variable.

8 15 1.875
64 127 1.984
1024 2047 1.999
1000000 1999993 2.0

The third column is the count divided by n, and it settles at 2. The count is about 2n, not n log n. Why? The inner loop runs n, then n/2, then n/4, and so on. The total is n + n/2 + n/4 + ... + 1, a geometric series, a sum where each term is a constant fraction of the one before. It converges to about 2n. So the whole thing is O(n), not O(n log n), even though the outer loop runs log n times.

The reason: most of the work is in the first few passes. This is a case where "number of passes times work per pass" overestimates, because the work per pass shrinks. When the inner work shrinks geometrically, the first term dominates.

The geometric series sum is another formula to remember: 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1. The last term is about half of the total. We use it again in lesson four for dynamic arrays.

Pattern 6: loops with an early exit

A break or return inside a loop makes the cost depend on the input, so you talk about worst case.

(7, 1)
(30, 9)
(30, 9)
(None, 9)

Best case 1 step, worst case n steps. The class for the worst case is O(n). An early exit does not change the worst case; it only helps on lucky inputs.

Pattern 7: while loops where the change is not obvious

Some loops hide their progress in a condition or a variable that changes in two places. Two examples:

(6, 3)
(21, 3)
(1, 7)

This is the Euclidean algorithm for the greatest common divisor, the largest number that divides both. Each step replaces (a, b) by (b, a % b), and a classical result says the remainder falls at least by half every two steps. So it needs O(log(min(a, b))) steps. A pair of numbers near a billion needs a few dozen steps at most, and the third call above needed only 7, not a billion. You cannot see this from the loop header; you must reason about how the variables shrink.

The lesson: for a while loop, find the quantity that decreases or increases, and ask how fast. If it moves by a constant each pass, linear. If by a constant factor, logarithmic. If by an amount that itself depends on the data, you need a careful argument.

((1, 5), 3)
(None, 6)

The loop condition is left < right. Each pass moves one pointer one step closer, so the distance right - left shrinks by exactly 1 per pass. It starts at n - 1, so the loop runs at most n - 1 times: O(n). A nested pair of loops would take n^2; two pointers on a sorted list does the same job in one pass. You will meet this pattern again in the interview chapters. Step through the visualizer to see how the two ends approach each other.

Watch how the two markers never move backwards. That is what makes the total count linear: each index is passed at most once by each pointer.

A mixed example, step by step

Real functions combine several patterns. Here is one, analysed from the top.

24
88

Work through it with the method from the start of this lesson.

1. n is the length of the list.
2. Part 1 is a single pass: n steps.
3. Part 2 has a loop of n passes, each containing a halving loop. The halving loop depends only on n, not on i, so the cost is a multiplication: n * log2(n).
4. Part 3 is a triangle: 0 + 1 + ... + (n - 1) = n(n - 1)/2.
5. The three parts run one after another, so we add: n + n log n + n(n-1)/2.
6. The biggest term is n^2 / 2. Drop the constant. The function is O(n^2).

Now check the count against the program, using the extra counting each part adds to total. For n = 4 the list holds 1, 2, 3, 4, so part 1 adds their sum, 10. In part 2, the halving loop from j = 4 runs twice (4 becomes 2, then 2 becomes 1), so four outer passes add 8. Part 3 adds 0 + 1 + 2 + 3 = 6. The total is 10 + 8 + 6 = 24, which is what the program printed. For n = 8, part 1 adds 36, part 2 adds 8 * 3 = 24, and part 3 adds 28, giving 88.

Notice how little the parts of lower order matter as n grows. At n = 8 the triangle is already the biggest part after the sum, and at n = 1,000 the triangle makes 499,500 steps, while the halving part makes only 10,000.

Summary table for loops

Here are the patterns in one place.

Keep this table in your head or on a card. About ninety percent of the loops in everyday code are on it.

From loops to recursion

A recursive function calls itself on a smaller version of the problem. We cannot count loop passes here, because the repetition is hidden inside the calls. Instead we write a recurrence relation: an equation that gives the cost of a call of size n in terms of the cost of smaller calls.

Let T(n) be the number of steps a call with input size n takes. Then:

1. Find the base case and its cost. That is T(1) or T(0), usually a constant.
2. Find how many recursive calls there are and how much smaller each input is.
3. Find the extra work done outside the recursive calls, such as splitting or combining.
4. Write T(n) = (calls) * T(smaller size) + (extra work).

Then solve the recurrence. We will use two methods that need no advanced maths: unrolling (substitute the formula into itself until a pattern appears) and the recursion tree (draw all calls and add the work on each level).

Example 1: factorial

1 1 1
5 120 5
10 3628800 10
20 2432902008176640000 20

One call per level, extra work is a constant (one multiplication). So

T(n) = T(n - 1) + 1, with T(1) = 1.

Unroll: T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = T(n-3) + 3 = ... = T(1) + (n - 1) = n.

The function makes n calls, each doing constant work: O(n) time. The printed counter agrees: for n = 20 there were 20 calls.

Example 2: sum with a loop inside each call

Let the extra work grow. This function sums a list recursively by slicing off the first item.

10 55
100 5050
500 125250

Each call copies the rest of the list, so the extra work is about n: T(n) = T(n - 1) + n. Unroll: T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2. That is O(n^2), the same triangle as before. The counter shows 5,050 for n = 100 and 125,250 for n = 500, matching n(n+1)/2. (We stop at 500 because Python's default limit of about 1,000 nested calls would stop a deeper run.)

This is a real trap. The recursive idea is linear, but the slice makes each call cost O(n). Passing an index instead of a slice brings it back to O(n).

10 11
100 101
500 501

The count is n + 1: linear. Recursion cost depends on the extra work in each call, not just the number of calls.

Example 3: binary search

Binary search compares with the middle and recurses on one half. One call on half the size, constant extra work:

T(n) = T(n / 2) + 1, with T(1) = 1.

Unroll: T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = ... = T(1) + k, where n / 2^k = 1, so k = log2(n). The answer is O(log n).

0 0 10
511 511 1
1023 1023 11
5000 -1 12

No more than 12 calls for 1,024 items: log2(1024) + 1 = 11 calls to shrink the range to nothing, plus one final call that sees the empty range. Each call is cheap because it passes the bounds, not a copied half.

Example 4: merge sort and the recursion tree

Merge sort splits in half, sorts each half and merges. Two calls on half size, plus a linear merge:

T(n) = 2T(n / 2) + n.

Unrolling is messier here, so draw the recursion tree. The top call has work n. It makes two calls of size n/2, each with work n/2: together n. The next level has four calls of n/4: together n again. Every level adds up to n. The number of levels is log2(n). So the total is n * log2(n).

Recursion tree for merge sort on eight items showing eight units of work on each level

The check: for n = 8 the picture shows 8 units on each of 4 rows (3 splitting levels plus the leaves), about 8 * 3 = 24 comparisons at most. This is the "every level costs the same" pattern, and it is the most useful picture in recursion analysis. When the recursion tree has equal work per level, the answer is work-per-level times number of levels.

Example 5: fast exponentiation

To compute x ** n you could multiply n times (O(n)). A faster idea: x ** n equals (x ** (n/2)) ** 2 when n is even, and x * x ** (n-1) when n is odd.

10 1024 5
100 698635 8
1000 783922 11
1000000 21861 21

Each line prints n, the power modulo 1,000,007 (only to keep the numbers small) and the number of calls. The call counts are about log2(n) + 1: 21 calls for n = one million. The recurrence is T(n) = T(n / 2) + 1, the same as binary search: O(log n). We used one recursive call and reused its result (half), which is the key. If we had written power(x, n // 2) * power(x, n // 2), there would be two calls per level, and the recurrence T(n) = 2T(n/2) + 1 solves to O(n), losing all the benefit.

Example 6: Fibonacci, and the tower of Hanoi

Naive Fibonacci has two recursive calls on sizes n - 1 and n - 2 and constant extra work:

T(n) = T(n - 1) + T(n - 2) + 1.

Each call produces two. Even the crude bound T(n) <= 2 * T(n - 1) gives O(2^n). The exact growth is about 1.618^n, the golden ratio, as the call counts in lesson two showed.

The tower of Hanoi puzzle moves n discs between pegs, where a bigger disc can never sit on a smaller one. To move n discs: move n - 1 to a spare peg, move the biggest, move the n - 1 again.

7
[('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]
1 1
5 31
10 1023
20 1048575

The recurrence is T(n) = 2T(n - 1) + 1. Unroll: T(n) = 2T(n-1) + 1 = 4T(n-2) + 2 + 1 = 8T(n-3) + 4 + 2 + 1 = ... = 2^n - 1. The answer is O(2^n), and it is not a flaw in the algorithm: any correct solution needs 2^n - 1 moves. A 64-disc tower would need 18 quintillion moves.

Compare Example 6 with Example 3. Both recursions shrink the input by a step. Hanoi makes two calls and doubles the work at each level, getting an exponential. Binary search makes one call and halves, getting a logarithm. The number of recursive calls and the size reduction decide the class.

The recurrence cheat sheet

You can recognise most recurrences by form. This table is worth knowing.

Two rows look alike and have different answers: T(n) = T(n/2) + n gives O(n), the geometric sum n + n/2 + n/4 + ... = 2n; T(n) = 2T(n/2) + n gives O(n log n), because the work per level does not shrink.

For the recurrences of the form T(n) = a T(n / b) + n^d, a rule called the master theorem gives the answer by comparing a with b^d. If a < b^d, the top level dominates and the answer is n^d. If a = b^d, every level costs the same and the answer is n^d log n. If a > b^d, the bottom level dominates and the answer is n^(log_b a). Merge sort has a = 2, b = 2, d = 1, so a = b^d and the answer is n log n. You do not need the theorem to pass an interview, but you may be asked to name it.

What happens inside: the call stack and the work

When a function calls itself, the computer saves the current call's state, its local variables and where to return, in a block on the call stack, then runs the new call. When a call returns, its block is removed and the saved state resumes. The cost of recursion therefore has two parts: the time of all the calls, which we just analysed, and the space of the stack, which grows with the depth of recursion. The next lesson analyses the space. For now, notice that each recursive call costs a little more than a loop pass, because setting up a stack block takes work. That is why a loop is often a constant factor faster than the equivalent recursion, even though the Big-O is the same.

Step through the visualizer for a recursive function, and count blocks on the stack at the deepest point.

Watch how each call piles up on the stack before any call returns, then they unwind in reverse order. The height of the pile at its tallest is the recursion depth, and the total number of calls made is what we have been counting for time. Those are two different numbers: factorial has depth n and n calls, while the Fibonacci tree has depth n but over a billion calls.

Common mistakes

Mistake 1: reading the loop header and stopping. A header like for i in range(n) tells you the outer count, but the body might contain another loop, a slice, a sorted call or a recursive call. Read the body before you decide.

Mistake 2: treating every nested loop as n * n. Dependent loops give a triangle, which is n(n-1)/2, and a halving inner loop gives log n. Multiply only when the inner count is independent of the outer variable.

Mistake 3: treating T(n) = 2T(n/2) + n and T(n) = T(n/2) + n as the same. The first has two calls per level, so every level costs n. The second has one call, so levels shrink geometrically. They give n log n and n.

Mistake 4: ignoring slices and copies in recursion. items[1:] copies the list. A recursive function that passes slices does extra work each call, turning O(n) into O(n^2) as in Example 2. Pass indices instead.

Mistake 5: counting calls and forgetting the work per call. Merge sort has about 2n calls, but the total time is n log n because the calls on the larger levels do real merging work. Time is the sum of work over all calls, not the number of calls.

Mistake 6: forgetting overlapping subproblems. Fibonacci computes fib(3) many times. The recurrence reveals it: two calls both of size about n, so the tree doubles each level. Memoisation, storing answers, cuts it to O(n).

Real error messages for this lesson. The common failure of recursion is running out of stack.

RecursionError: maximum recursion depth exceeded

Python raises it when the depth passes its limit (usually 1,000). It means either the base case is missing or wrong, so the function never stops, or the input is deep enough that the function needs more levels than Python allows. For a missing base case, check the condition that should stop the recursion. For deep input, rewrite the recursion as a loop.

RecursionError: maximum recursion depth exceeded while calling a Python object

The same error appears in a slightly different form when the limit is hit during a call into built-in code.

In Java or C++ the equivalent failures are java.lang.StackOverflowError and a crash called a segmentation fault. Their cause is the same, and the same fix applies.

If you write a recurrence and your unrolled answer disagrees with the counter, there is no error message. Compare the first few values of your formula with the counter by hand. A disagreement in the first three values usually means an off-by-one in the base case.

A debugging walkthrough: the function that got slow in the middle

A teammate says: "count_inversions is fine for 1,000 items and takes 10 minutes for 100,000". An inversion is a pair of positions where a bigger number comes before a smaller one. The function counts them.

3
10
0

Step 1: n is the list length. Step 2: there is a dependent double loop, a triangle: n(n-1)/2 comparisons. For n = 1,000 that is 499,500, instant. For n = 100,000 that is 5 * 10^9, minutes in Python. The slowness is the quadratic class, no surprise.

Step 3: can we do better? Think of merge sort. During the merge step, when we take an item from the right half, every remaining item in the left half is bigger and forms an inversion with it. So we can count inversions while we sort, at no extra Big-O cost.

3
10
0

The recurrence is T(n) = 2T(n/2) + n, so O(n log n). For n = 100,000 that is about 1.7 million steps instead of 5 billion. The same answers, thousands of times faster. The technique to remember: when a quadratic loop counts pairs, ask whether a sorted order or a merge can count them in bulk.

Where this shows up in real life and interviews

Interviews. "What is the time complexity of this recursive function?" is a very common question. The ask is to produce the recurrence aloud, solve it with the tree and name the class. Practise saying: "Two calls on half the size plus linear merging, so each level costs n and there are log n levels."

Real code. Directory walkers, JSON parsers, game AIs, and compilers are all recursive. Knowing that a recursive call that copies its input is quadratic helps you avoid slowdowns in code that processes trees or nested data.

Debugging performance. When a recursive function is slow, count calls with a counter, as we did in every example. If the number of calls is far above n, you have overlapping subproblems and should memoise. If the calls are about n but the time is quadratic, look for copying in each call.

Practice

1. (Easy) How many times does count += 1 run? Give the value for n = 10 and the class.

for i in range(0, n, 2):
    count += 1

2. (Easy) Give the complexity of for i in range(n): for j in range(5): ....

3. (Easy) Write the recurrence and the class for def f(n): return 0 if n == 0 else 1 + f(n - 1).

4. (Medium) Compute exactly how many times the body runs and name the class.

i = n
while i > 0:
    for j in range(3):
        work()
    i //= 2

5. (Medium) Count the body runs for n = 5 and give the class.

for i in range(1, n + 1):
    for j in range(i, n + 1):
        count += 1

6. (Medium) Solve T(n) = T(n - 1) + n by unrolling for n = 4 with T(0) = 0, then generalise.

7. (Medium) What is the complexity of this function? Does the answer change if we replace the list slices with indexes?

def has_item(items, target):
    if not items:
        return False
    if items[0] == target:
        return True
    return has_item(items[1:], target)

8. (Medium) Is this O(n) or O(n log n)? Count for n = 8.

def f(n):
    if n <= 1:
        return 1
    return f(n // 2) + f(n // 2) + 1

9. (Hard) Find the class of this function and prove it with a count.

def g(n):
    count = 0
    i = 1
    while i < n:
        j = 0
        while j < i:
            count += 1
            j += 1
        i *= 2
    return count

7 1023 1048575

10. (Hard) The recurrence T(n) = 3T(n / 2) + n describes the Karatsuba method for multiplying big numbers. Use the master theorem to give its class.

11. (Hard) Count the exact number of calls of fib made by this memoised version for n = 10 and explain the class.

def fib_memo(n, memo, counter):
    counter[0] += 1
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo, counter) + fib_memo(n - 2, memo, counter)
    return memo[n]

55 19

What you now know

• The loop method is: count how many times the innermost statement runs, summing over the outer passes when the inner count depends on the outer variable.
• Single loops are linear, independent nested loops multiply, triangles give n(n-1)/2, halving or doubling gives log n, and a shrinking geometric series gives O(n).
• The recursion method is: write T(n) in terms of smaller calls plus extra work, then unroll it or draw the recursion tree and add the work per level.
• The number of recursive calls and how much each one shrinks the input decide the class: one call that halves is log n, two calls that halve with linear work is n log n, two calls that each remove one step is exponential.
• Slicing in recursion copies data, and counters in code let you check every analysis against the real count.