Algorithm Analysis

1.1 Asymptotic Notation

Definition. $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Definition. $f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $f(n) \geq c \cdot g(n)$ for all $n \geq n_0$.

Definition. $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

Definition. $f(n) = o(g(n))$ if $\lim_{n \to \infty} f(n)/g(n) = 0$.

Definition. $f(n) = \omega(g(n))$ if $\lim_{n \to \infty} g(n)/f(n) = 0$.

Theorem 1.1. $f(n) = O(g(n))$ if and only if $g(n) = \Omega(f(n))$.

Proof. Suppose $f(n) = O(g(n))$. Then there exist $c, n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$Hence $g(n) \geq (1/c) \cdot f(n)$ for all $n \geq n_0$So $g(n) = \Omega(f(n))$. The converse follows by symmetry. $\blacksquare$

Theorem 1.2. $f(n) = \Theta(g(n))$ if and only if there exist constants $c_1, c_2 > 0$ and $n_0$ such that $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$ for all $n \geq n_0$.

Proof. By definition, $f(n) = \Theta(g(n))$ means $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. The former gives $f(n) \leq c_2 \cdot g(n)$ for some $c_2 > 0$And the latter gives $f(n) \geq c_1 \cdot g(n)$ for some $c_1 > 0$. Combining yields the stated inequality. $\blacksquare$

Theorem 1.3 (Limit Rule). If $\lim_{n \to \infty} f(n)/g(n) = c$ where $0 < c < \infty$Then $f(n) = \Theta(g(n))$. If $c = 0$Then $f(n) = O(g(n))$. If $c = \infty$Then $g(n) = O(f(n))$.

Proof. If $c = 0$Then for any $\varepsilon > 0$There exists $n_0$ such that $f(n)/g(n) < \varepsilon$ for all $n \geq n_0$So $f(n) \leq \varepsilon \cdot g(n)$Establishing $f(n) = O(g(n))$. If $0 < c < \infty$Take $\varepsilon = c/2$; then $(c/2) \cdot g(n) \leq f(n) \leq (3c/2) \cdot g(n)$ for sufficiently large $n$Giving $\Theta$. The $c = \infty$ case is symmetric. $\blacksquare$

Proposition 1.4. Asymptotic notation is transitive: if $f = O(g)$ and $g = O(h)$Then $f = O(h)$.

Proof. There exist $c_1, n_1$ with $f(n) \leq c_1 g(n)$ for $n \geq n_1$And $c_2, n_2$ with $g(n) \leq c_2 h(n)$ for $n \geq n_2$. Then $f(n) \leq c_1 c_2 h(n)$ for $n \geq \max(n_1, n_2)$. $\blacksquare$

Proposition 1.5. $O$-notation is reflexive: $f = O(f)$ for all $f$.

Proof. Take $c = 1$ and $n_0 = 1$. Then $f(n) \leq 1 \cdot f(n)$ for all $n \geq 1$. $\blacksquare$

for i = 1 to n:
    for j = i to n:
        constant-time work

for i = 1 to n:
    j = 1
    while j < n:
        j = j * 2
        constant-time work

for i = 1 to n:
    for j = 1 to i:
        for k = 1 to j:
            constant-time work

1.2 Common Complexity Classes

Proposition 1.6. These classes form a strict hierarchy: $O(1) \subsetneq O(\log n) \subsetneq O(n) \subsetneq O(n \log n) \subsetneq O(n^2) \subsetneq O(n^3) \subsetneq O(2^n) \subsetneq O(n!)$

1.3 Recurrences and the Master Theorem

Many divide-and-conquer algorithms yield recurrences of the form:

$T(n) = aT(n/b) + f(n)$

Where $a \geq 1$ is the number of subproblems, $b > 1$ is the factor by which the input is divided, and $f(n)$ is the cost of dividing and combining.

Theorem 1.7 (Master Theorem). Let $a \geq 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence $T(n) = aT(n/b) + f(n)$Where we interpret $n/b$ to mean either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$. Let $c = \log_b a$. Then:

1. If $f(n) = O(n^{c - \varepsilon})$ for some $\varepsilon > 0$Then $T(n) = \Theta(n^c)$.
2. If $f(n) = \Theta(n^c \log^k n)$ for some $k \geq 0$Then $T(n) = \Theta(n^c \log^{k+1} n)$.
3. If $f(n) = \Omega(n^{c + \varepsilon})$ for some $\varepsilon > 0$And if $a f(n/b) \leq q f(n)$ for some constant $q < 1$ and all sufficiently large $n$ (the regularity condition), then $T(n) = \Theta(f(n))$.

Proof (Case 1 sketch). The recursion tree has depth $\log_b n$. At level $i$There are $a^i$ nodes, each costing $f(n/b^i)$. Since $f(n) = O(n^{c - \varepsilon})$The cost at level $i$ is $a^i \cdot (n/b^i)^{c - \varepsilon} = n^{c - \varepsilon} \cdot (a / b^{c - \varepsilon})^i$. The total cost is dominated by the leaves (level $\log_b n$), which contribute $a^{\log_b n} = n^c$. The internal levels contribute a geometric series with ratio $a / b^{c - \varepsilon} = b^\varepsilon > 1$So the leaf level dominates. $\blacksquare$

1.4 Amortised Analysis

Amortised analysis gives the average cost per operation over a sequence of operations, even when Individual operations may be expensive.

Methods:

1. Aggregate analysis: Compute total cost of $n$ operations, divide by $n$.
2. Accounting method: Assign an amortised cost to each operation; the sum of amortised costs must be an upper bound on the total actual cost.
3. Potential method: Define a potential function $\Phi$; the amortised cost of the $i$-th operation is $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$.

Theorem 1.8 (Potential Method). If $\Phi(D_i) \geq \Phi(D_0)$ for all $i \geq 1$Then the total amortised cost $\sum_{i=1}^{n} \hat{c}_i$ is an upper bound on the total actual cost $\sum_{i=1}^{n} c_i$.

Proof. $\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} (c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0) \geq \sum_{i=1}^{n} c_i$. $\blacksquare$

Example (Dynamic Array). A dynamic array doubles in size when full. Insertion is $O(1)$ Amortised: most insertions cost $O(1)$; occasional resizing costs $O(n)$But is paid for by the Surplus from previous $O(1)$ insertions.

:::caution Common Pitfall Amortised analysis gives a guarantee over a sequence of operations, not a per-operation worst-case bound. A single operation can still be expensive (e.g., a resize in a dynamic array costs $O(n)$). Amortised bounds are meaningful only when the sequence length is not bounded by a constant.

:::