The Method for Computing Complexity

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)$.

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.

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.