Algorithm Analysis — Asymptotic Notation and Recurrences

Measuring running time by counting operations, best/worst/average cases, Big-O, Ω and Θ with their properties, the growth-rate hierarchy, counting loops (nested, logarithmic, dependent), solving recurrences by substitution, recursion trees and the master theorem, amortised analysis, and space complexity.

What we measure

Running time is measured by counting basic operations (comparisons, assignments, arithmetic) as a function of the input size $n$ , ignoring machine-dependent constants.

Worst case: maximum over all inputs of size $n$ (the usual guarantee).
Best case: minimum (e.g. insertion sort on sorted input: $n - 1$ comparisons).
Average case: expectation over a distribution of inputs (quicksort: $\approx 1.39\,n\log_2 n$ comparisons on random input).

Asymptotic notation

Notation	Meaning	Informally
$f = O(g)$	$\exists c, n_0: f(n) \le c\,g(n)\ \forall n \ge n_0$	$f$ grows at most like $g$
$f = \Omega(g)$	$\exists c, n_0: f(n) \ge c\,g(n)\ \forall n \ge n_0$	at least like $g$
$f = \Theta(g)$	both $O$ and $\Omega$	exactly like $g$
$f = o(g)$	$f/g \to 0$	strictly slower
$f = \omega(g)$	$f/g \to \infty$	strictly faster

Properties: transitivity; $O(f) + O(g) = O(\max(f, g))$ ; constants and lower-order terms vanish ( $3n^2 + 10n\log n + 7 = \Theta(n^2)$ ); logarithm bases differ by constants ( $\log_2 n = \Theta(\log_{10}n)$ ), but exponential bases do not ( $2^n \ne \Theta(3^n)$ ).

Limit test: if $\lim f/g = c$ with $0 < c < \infty$ , then $f = \Theta(g)$ ; if the limit is 0, $f = o(g)$ .

The growth hierarchy

1 \ll \log\log n \ll \log n \ll \sqrt n \ll n \ll n\log n \ll n^2 \ll n^3 \ll 2^n \ll n! \ll n^n

$n$	$\log_2 n$	$n\log_2 n$	$n^2$	$2^n$
10	3.3	33	100	1024
1000	10	$10^4$	$10^6$	$\approx 10^{301}$
$10^6$	20	$2\times10^7$	$10^{12}$	—

Counting loops

Loop shape	Iterations
`for i in range(n)`	$n$
nested `for i in range(n): for j in range(n)`	$n^2$
`for i in range(n): for j in range(i)`	$\frac{n(n-1)}{2}$
`i = 1; while i < n: i *= 2`	$\lceil\log_2 n\rceil$
`i = n; while i > 0: i //= 2`	$\lfloor\log_2 n\rfloor + 1$
`for i in range(n): j = 1; while j < n: j *= 2`	$n\log n$
`i = 1; while i * i <= n: i += 1`	$\sqrt n$

Worked example

Python

s = 0
i = 1
while i <= n:
    for j in range(i):
        s += 1
    i *= 2

The inner loop runs $1 + 2 + 4 + \dots + 2^{\lfloor\log_2 n\rfloor} < 2n$ times in total: $\Theta(n)$ , not $\Theta(n\log n)$ . Dependent loops must be summed, not multiplied.

Recurrences

Recursive algorithms give recurrences. Three ways to solve them:

1. Unrolling / substitution: $T(n) = T(n-1) + c \Rightarrow T(n) = cn$ ; $T(n) = 2T(n-1) + c \Rightarrow \Theta(2^n)$ (Towers of Hanoi: $2^n - 1$ moves).

2. Recursion tree: sum the work level by level.

Each level of merge sort's recursion tree does n total work.

3. Master theorem for $T(n) = aT(n/b) + f(n)$ with $a \ge 1$ , $b > 1$ . Compare $f(n)$ with $n^{\log_b a}$ :

Case	Condition	$T(n)$
1	$f(n) = O(n^{\log_b a - \epsilon})$ (leaves dominate)	$\Theta(n^{\log_b a})$
2	$f(n) = \Theta(n^{\log_b a}\log^k n)$ , $k \ge 0$ (balanced)	$\Theta(n^{\log_b a}\log^{k+1}n)$
3	$f(n) = \Omega(n^{\log_b a + \epsilon})$ and $af(n/b) \le cf(n)$ , $c < 1$ (root dominates)	$\Theta(f(n))$

Recurrences worth memorising

Recurrence	Solution	Algorithm
$T(n) = T(n/2) + 1$	$\Theta(\log n)$	binary search
$T(n) = T(n-1) + 1$	$\Theta(n)$	linear recursion, linear search
$T(n) = 2T(n/2) + 1$	$\Theta(n)$	tree traversal
$T(n) = 2T(n/2) + n$	$\Theta(n\log n)$	merge sort, balanced quicksort
$T(n) = T(n-1) + n$	$\Theta(n^2)$	worst-case quicksort, selection sort
$T(n) = 2T(n-1) + 1$	$\Theta(2^n)$	Towers of Hanoi
$T(n) = T(n-1) + T(n-2) + 1$	$\Theta(\varphi^n)$ , $\varphi \approx 1.618$	naive Fibonacci
$T(n) = T(\sqrt n) + 1$	$\Theta(\log\log n)$

Amortised analysis

The average cost per operation over a worst-case sequence of operations. Example: a dynamic array (Python list) doubles its capacity when full; a single append may cost $O(n)$ for copying, but $n$ appends cost $O(n)$ in total, so each is amortised $O(1)$ .

Space complexity

Extra memory used besides the input: merge sort $O(n)$ , quicksort $O(\log n)$ expected for the recursion stack, heapsort and insertion sort $O(1)$ . Recursion depth counts as space.