---
title: 'The Method for Computing Complexity'
source: 'https://academia.sh/en/courses/algorithms/computing-complexity'
course: Algorithms
language: en
updated: '2026-08-17T18:07:33+00:00'
license: 'CC BY-SA 4.0'
---

# The Method for Computing Complexity

Counting cost with loop and conditional rules, recurrence relations, the master theorem, and amortized analysis.

The classes have been recognized; next comes determining which class a piece of code
belongs to by looking at it. This lesson gives the rules for the calculation. The
rules are few and are applied in combination.

## Basic Rules

**Sequential parts are added.** If two parts run one after the other, their costs
are added, and the larger one dominates: $O(n) + O(n^2) = O(n^2)$.

**A loop is body cost times iteration count.** A loop with a constant body that
runs $n$ times is $O(n)$.

**In nested loops, costs multiply.** Two loops, each running $n$ times, are
$O(n^2)$.

**In conditional structures, the worst branch is taken.** The guarantee is given
over the worst case.

**A constant number of repetitions is constant.** A loop whose iteration count does
not depend on $n$ is $O(1)$.

```python
def counting_examples(n: int) -> dict[str, int]:
    counters = {"single": 0, "nested": 0, "triangular": 0, "halving": 0}

    for i in range(n):                       # O(n)
        counters["single"] += 1

    for i in range(n):                       # O(n²)
        for j in range(n):
            counters["nested"] += 1

    for i in range(n):                       # O(n²) — triangular, but still quadratic
        for j in range(i):
            counters["triangular"] += 1

    i = 1
    while i < n:                             # O(log n)
        counters["halving"] += 1
        i *= 2

    return counters


print(counting_examples(8))
# {'single': 8, 'nested': 64, 'triangular': 28, 'halving': 3}
print(counting_examples(16))
# {'single': 16, 'nested': 256, 'triangular': 120, 'halving': 4}
```

When the input doubles, the counts change as the classes predict: single doubles,
nested quadruples; the halving loop only increases by one.

The triangular loop needs attention. The total iteration count is $n(n-1)/2$; once
the constant factor is eliminated, $O(n^2)$ remains. The observation "it runs about
half as many times" does not change the class — it only changes the constant.

## How the Loop Bound Changes

The iteration count depends on how the loop variable advances:

| Advancement | Iteration count | Class |
|---|---|---|
| `i += 1` | $n$ | $O(n)$ |
| `i += k` | $n/k$ | $O(n)$ |
| `i *= 2` | $\log_2 n$ | $O(\log n)$ |
| `i = i * i` | $\log \log n$ | $O(\log \log n)$ |
| `i -= 1` (from n) | $n$ | $O(n)$ |

The second row matters: advancing by a constant step does not change the class.
Multiplicative advancement does; this is the source of binary search's logarithmic
behavior.

## Recurrence Relations

A recursive algorithm's cost is written in terms of itself. This expression is
called a **recurrence relation**.

Three common patterns:

$$
T(n) = T(n-1) + O(1) \implies T(n) = O(n)
$$

At every step the problem shrinks by one element and constant work is done; a
total of $n$ steps. Factorial computation is of this pattern.

$$
T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)
$$

At every step the problem is halved and constant work is done; the number of
halvings is $\log_2 n$. Binary search is of this pattern.

$$
T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n)
$$

The problem is split into two halves, and all elements are processed at every
level. Merge sort is of this pattern, and it is the main example of the next topic.

## Recursion Tree

The intuitive way to solve a relation is to draw the calls as a tree and sum the
cost level by level.

For the relation $T(n) = 2T(n/2) + n$:

| Level | Call count | Work per call | Level total |
|---|---|---|---|
| 0 | 1 | $n$ | $n$ |
| 1 | 2 | $n/2$ | $n$ |
| 2 | 4 | $n/4$ | $n$ |
| $k$ | $2^k$ | $n/2^k$ | $n$ |

Every level's total is $n$, and the number of levels is $\log_2 n$; the total comes
out to $n \log n$.

The same method gives a different result for $T(n) = 2T(n/2) + O(1)$: the level
totals grow as $1, 2, 4, \dots, n$, and the total comes out to $O(n)$. The leaf
count becomes dominant.

## The Master Theorem

Most divide-and-conquer relations fit a single pattern:

$$
T(n) = a\,T(n/b) + f(n)
$$

Here $a$ is the number of subproblems, $b$ is the shrink factor, and $f(n)$ is the
cost of splitting and combining. The result is determined by comparing $f(n)$ with
$n^{\log_b a}$:

- If $f(n)$ is smaller: $T(n) = \Theta(n^{\log_b a})$ — the leaves dominate.
- If the two are of the same order: $T(n) = \Theta(n^{\log_b a} \log n)$ — all
  levels are equal.
- If $f(n)$ is larger: $T(n) = \Theta(f(n))$ — the root dominates.

In merge sort, $a = 2$, $b = 2$, $f(n) = n$; since $n^{\log_2 2} = n$, the second
case applies, and the result comes out to $\Theta(n \log n)$.

The theorem's full statement contains additional conditions, and not every relation
fits this pattern; for those that do not, the tree method or a direct solution is
used.

## Amortized Analysis

The cost of some operations is misleading when looked at individually. The dynamic
array from the Data Structures course was an example of this: appending is mostly
constant, occasionally linear.

The **aggregate method** computes the total cost of $m$ operations and divides by
$m$. In a dynamic array, the total copying for $n$ appends was less than $n$; the
amortized cost per append is constant.

```python
def total_copies(n: int) -> int:
    """The total number of copies made over n appends (capacity doubling each time)."""
    capacity, length, copies = 1, 0, 0
    for _ in range(n):
        if length == capacity:
            copies += length               # every element is moved to the new block
            capacity *= 2
        length += 1
    return copies


for n in (16, 1000, 100_000):
    print(n, total_copies(n), f"{total_copies(n)/n:.2f}")
# 16 15 0.94
# 1000 1023 1.02
# 100000 131071 1.31
```

The average number of copies per append stays around a small constant as the input
grows; it does not grow linearly. The statement "amortized constant cost" says
exactly this.

There are two more methods. The **accounting method** charges every cheap
operation a share for expensive work to come; the **potential method** expresses
the structure's "stored energy" with a function. All three give the same result;
the choice depends on which one makes the proof shorter.

## Order of Application

The sequence followed to find the cost of a piece of code:

1. **Define the input size.** What does $n$ count?
2. **Find the innermost operation.** Which operation repeats most often?
3. **Multiply the iteration counts.** From outside to inside in nested structures.
4. **Add the sequential parts**, take the largest term.
5. **If there is recursion, write the relation** and solve it.
6. **If there is amortized behavior**, divide total cost by operation count.

When the steps are applied in order, the result is obtained without resorting to
intuition.

## Summary

- Sequential parts are added, costs multiply in nested loops, and the worst branch
  is taken in conditionals.
- Multiplicative advancement of the loop variable makes the iteration count
  logarithmic; advancing by a constant step does not change the class.
- Recursive cost is written as a relation; three common patterns give linear,
  logarithmic, and linearithmic results.
- The recursion tree solves the relation by summing cost level by level.
- The master theorem classifies divide-and-conquer relations into three cases.
- Amortized analysis divides the total cost of a sequence of operations by the
  operation count.

## Next Step

So far, only time has been considered. Yet algorithms also use memory, and the two
frequently substitute for one another: it is possible to run faster by using more
memory, or slower by using less. The next lesson takes up this trade-off and its
typical patterns.