Program Complexity

Computing the complexity of a program requires structural induction on its
syntax. The rules mirror the structure of the language:

Base cases:
- Constants and variables: $O(1)$ — they evaluate in one step.

Arithmetic operations: $+, -, *, /$ — $O(1)$ per operation (one machine
instruction).

Function application: $f(x_1, \dots, x_k)$ — cost of evaluating each
argument plus the function body.

Sequential composition $\alpha_1; \alpha_2; \dots; \alpha_k$:

Branching if P then alpha1 else alpha2:

Loops — for for i := 1 to n do alpha:

Recursion $f(x) = \dots f(\text{smaller}) \dots$:
Set up a recurrence $T(n)$ and solve it. Examples:
- Linear recursion $T(n) = T(n-1) + 1 = O(n)$.
- Binary recursion (divide & conquer) $T(n) = 2 T(n/2) + n = O(n \log n)$.

Examples:
- Linear search on a list of $n$: $T(n) = O(n)$.
- Binary search: $T(n) = T(n/2) + 1 = O(\log n)$.
- Selection sort: $T(n) = n + (n-1) + \dots + 1 = O(n^2)$.
- Merge sort: $T(n) = 2T(n/2) + n = O(n \log n)$.

To compute the time complexity of nested loops, count iterations.

Pattern 1: Single loop.

Total work: $\sum_{i=1}^{n} 1 = n$. Complexity: $O(n)$.

Pattern 2: Nested loops.

Total work: $\sum_{i=1}^{n} \sum_{j=1}^{n} 1 = \sum_{i=1}^{n} n = n^2$. Complexity: $O(n^2)$.

Pattern 3: Triangular nested loops.

Total work: $\sum_{i=1}^{n} \sum_{j=1}^{i} 1 = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Complexity: $O(n^2)$ (the leading term dominates).

Pattern 4: Loop with shrinking inner bound.

Total work: $\sum_{i=1}^{n} (n - i) = \sum_{k=0}^{n-1} k = \frac{(n-1)n}{2}$. Complexity: $O(n^2)$.

Pattern 5: Logarithmic inner loop.

Inner loop runs $O(\log n)$ times. Total: $n \cdot O(\log n) = O(n \log n)$.

Reading. Each pattern reduces to a summation; identify the closed form; take the leading term. The summation $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ is the most common.