Analysing iterative and recursive algorithms

With asymptotic notation in hand, we can analyse real code. Iterative algorithms are analysed by counting how many times each loop body runs, which turns code into a summation. Recursive algorithms are analysed by writing a recurrence, an equation that expresses the running time on input size \(n\) in terms of the running time on smaller inputs, and then solving it. This lesson develops the summations you will need most often, three methods for solving recurrences, and the master theorem, which settles the recurrences that arise from most divide-and-conquer algorithms in one step.

Loops become sums

A loop that runs \(n\) times with a constant amount of work per iteration costs \(\Theta(n)\). When the work per iteration varies, add up the work iteration by iteration. The resulting sum may be one of a small family of standard forms. You proved several of these by induction in CMPUT-272 lesson 10; here they become tools.

Two patterns are worth memorizing. In an arithmetic series the terms grow by a constant, and the sum is the number of terms times the average term, so it is one degree higher than the largest term divided by \(n\). In a geometric series the terms grow by a constant factor, and the sum is within a constant factor of its largest term. That second fact is behind many surprising results, such as building a heap in linear time (lesson 5) and the amortized cost of a growing array (lesson 12).

def count_nested(n):
    c = 0
    for i in range(n):
        for j in range(i, n):
            c += 1
    return c

def count_doubling(n):
    c = 0
    i = 1
    while i < n:
        c += 1
        i *= 2
    return c

def count_doubling_inner(n):
    c = 0
    i = 1
    while i < n:
        for j in range(i):       # inner work grows with i
            c += 1
        i *= 2
    return c

for n in (10, 100, 1000, 1024):
    print(n, count_nested(n), n * (n + 1) // 2,
          count_doubling(n), count_doubling_inner(n))

10 55 55 4 15
100 5050 5050 7 127
1000 500500 500500 10 1023
1024 524800 524800 10 1023

The second function shows the logarithmic pattern: a counter that doubles from 1 reaches \(n\) after \(\lceil \log_2 n \rceil\) steps, so 1000 takes 10 iterations. The third function is a trap for careless analysis. Its outer loop runs \(\Theta(\log n)\) times and its inner loop runs up to \(n\) times, so a quick product suggests \(\Theta(n \log n)\). But the inner loop runs \(1 + 2 + 4 + \cdots\) times, a geometric series dominated by its last term, which is less than \(n\). The total is less than \(2n\), so the function is \(\Theta(n)\), as the output confirms with 1,023 for both 1000 and 1024.

Recurrences from recursive code

For a recursive function, let \(T(n)\) be its worst-case running time on input size \(n\). Each call does some non-recursive work and makes recursive calls on smaller inputs, so \(T(n)\) equals the non-recursive work plus the sum of the recursive costs. The base case gives a constant. For merge sort, which lesson 4 studies in detail, the function splits a list of size \(n\) into two halves, sorts each recursively, and merges them in linear time:

We usually ignore floors and ceilings, writing \(n/2\) for \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil\), and we usually replace the constant \(c\) with 1, because neither changes the asymptotic answer for the recurrences in this course. Binary search, which looks at the middle element and recurses on one half, gives \(T(n) = T(n/2) + c\). A function that recurses on \(n - 1\) after a linear scan, such as a naive recursive selection sort, gives \(T(n) = T(n-1) + c\,n\).

Method 1: unrolling and the recursion tree

The most intuitive method is to expand the recurrence repeatedly and look for a pattern. For merge sort, the top call does \(cn\) work and makes two calls on size \(n/2\). Each of those does \(cn/2\) work and makes two calls on size \(n/4\), and so on. Drawing this as a tree, level \(i\) has \(2^i\) nodes, each doing \(cn/2^i\) work, so each level costs \(cn\) in total. The sizes halve until they reach 1, which takes \(\log_2 n\) levels below the root, so there are \(\log_2 n + 1\) levels.

The recursion tree tells you not only the answer but why. If the cost per level is the same at every level, the total is the per-level cost times the number of levels. If the cost per level shrinks geometrically as you go down, the root dominates and the total is within a constant of the root's cost. If the cost grows geometrically, the leaves dominate and the total is within a constant of the leaf level. These three shapes are exactly the three cases of the master theorem below.

Method 2: substitution

The substitution method guesses a bound and proves it by induction. It is the most powerful method, because it works for recurrences no formula covers, but it needs a good guess, often from a recursion tree. To prove \(T(n) \le c\, n \log_2 n\) for merge sort's recurrence \(T(n) = 2T(n/2) + n\) with \(T(1) = 1\), assume the bound holds for all smaller inputs, in the strong-induction style of CMPUT-272 lesson 10.

A classic pitfall in substitution is to prove a bound that is too weak to carry the induction. If you try to prove \(T(n) \le c\,n\) for the same recurrence, you get \(T(n) \le 2c(n/2) + n = cn + n\), which is not at most \(cn\). Writing \(cn + n = O(n)\) and declaring victory is wrong: the inductive hypothesis must be reproduced exactly, with the same constant, or the argument proves nothing.

Method 3: the master theorem

Divide-and-conquer algorithms usually produce recurrences of the form \(T(n) = a\,T(n/b) + f(n)\), where \(a \ge 1\) subproblems each have size \(n/b\) with \(b > 1\), and \(f(n)\) is the cost of dividing and combining. The master theorem compares \(f(n)\) with \(n^{\log_b a}\), the number of leaves in the recursion tree, and gives the answer directly in three cases. We state the common simplified version for \(f(n) = \Theta(n^d)\) with \(d \ge 0\).

In the first case the root dominates: dividing and combining at the top costs more than everything below it. In the second case every level costs about the same, giving a logarithmic factor. In the third case the leaves dominate, because the number of subproblems multiplies faster than their sizes shrink. The general theorem allows any \(f(n)\) and adds a regularity condition in the first case, but the simplified version covers every recurrence in this course.

import math
from functools import lru_cache

def master(a, b, d):
    e = math.log(a, b)
    if abs(d - e) < 1e-12:
        return f'Theta(n^{d} log n)'
    return f'Theta(n^{max(d, e):.3f})'

@lru_cache(maxsize=None)
def T(n, a, b, d):
    if n <= 1:
        return 1
    return a * T(n // b, a, b, d) + n ** d

for a, b, d in [(2, 2, 1), (1, 2, 0), (3, 2, 1), (7, 2, 2), (2, 2, 2)]:
    n1, n2 = 2 ** 10, 2 ** 11
    growth = T(n2, a, b, d) / T(n1, a, b, d)      # ratio when n doubles
    print(f'a={a} b={b} d={d}: {master(a, b, d):>18}, doubling ratio {growth:.3f}')

a=2 b=2 d=1:   Theta(n^1 log n), doubling ratio 2.182
a=1 b=2 d=0:   Theta(n^0 log n), doubling ratio 1.091
a=3 b=2 d=1:     Theta(n^1.585), doubling ratio 3.012
a=7 b=2 d=2:     Theta(n^2.807), doubling ratio 7.006
a=2 b=2 d=2:     Theta(n^2.000), doubling ratio 4.001

The doubling ratios match the predictions. For \(\Theta(n^k)\) the ratio when \(n\) doubles approaches \(2^k\): about 3 for \(n^{1.585}\), about 7 for \(n^{2.807}\) and about 4 for \(n^2\). For merge sort the ratio is a little above 2, as expected for \(n \log n\), and for binary search the value grows by only 1 each time \(n\) doubles, the signature of a logarithm.

When the master theorem does not apply

The theorem needs subproblems of equal size \(n/b\) with a constant \(b > 1\). It says nothing about \(T(n) = T(n-1) + n\), which shrinks by subtraction, not division. Unrolling that recurrence gives \(n + (n-1) + \cdots + 1 = \Theta(n^2)\), the cost of the naive recursive selection sort. Similarly \(T(n) = 2T(n-1) + 1\), the Towers of Hanoi recurrence, unrolls to \(2^n - 1\). The simplified theorem also misses \(f(n)\) that are not plain powers, such as \(T(n) = 2T(n/2) + n \log n\), whose solution \(\Theta(n \log^2 n)\) follows from a recursion tree in which level \(i\) costs \(n \log(n/2^i)\). Recurrences with unequal parts, such as \(T(n) = T(n/5) + T(7n/10) + n\) from lesson 6, are solved by substitution.