1.3 Asymptotic Bounds, Recurrence Relations, and Amortized Analysis

After completing Common Complexity Analysis, spend about 45 minutes distinguishing O, Ω, and Θ, expressing recursive programs as recurrence relations, and checking when the Master Theorem applies.

A Loose Upper Bound Is Not Enough

A linear scan can be described as O(n²) or even O(2ⁿ), but both bounds are loose. A correct upper bound alone does not identify the actual growth rate; tightness matters.

1. O, Ω, and Θ are bounds, not input cases

Let f(n) be a non-negative cost function under the chosen model, and let g(n) be positive for sufficiently large n.

• f(n) = O(g(n)): There exist positive constants c and a threshold n₀ such that all n ≥ n₀ satisfy f(n) ≤ c·g(n).
• f(n) = Ω(g(n)): There exist positive constants c and a threshold n₀ such that all n ≥ n₀ satisfy f(n) ≥ c·g(n).
• f(n) = Θ(g(n)): There exist both asymptotic upper and lower bounds; that is, eventually bounded between two constant multiples of g(n).

3n + 7 belongs to Θ(n) and also to O(n²). The former provides a tight bound, while the latter only gives a correct but looser upper bound.

Best, worst, and average cases form a separate axis. Linear search can exhibit:

Input Scenario	Cost Function	Tight Bound
Best: First item hit	1	Θ(1)
Worst: Last item hit or not found	n	Θ(n)
Average	Depends on target position and missing probability	Distribution must be specified first

"The worst case is O, the best case is Ω" is not a definition. You can assign Θ(n) to the worst-case cost, or O(1) to the best-case cost.

2. The Output Itself Provides a Lower Bound

When generating all unordered pairs of positions, the number of results is:

k = n(n - 1) / 2 = Θ(n²)

If the interface must explicitly return all k pairs, merely producing the output requires Ω(k) time and Θ(k) output space. A more clever loop cannot reduce this problem to linear time; unless the interface returns only a count, a lazy iterator, or a compressed representation. Fully consuming all k pairs from the iterator still requires Ω(k) time; laziness removes the need to store them all in advance.

Therefore, the complexity conclusion must specify:

1. Input size;
2. Cost model;
3. Best, worst, average, or expected case;
4. Measurement scope for input, output, and auxiliary space;
5. Assumptions about containers, hashing, or comparison operations.

3. Write the Recurrence First

With constant-cost comparisons and index-based ranges, worst-case binary search recurses into half the interval:

T(n) = T(n/2) + Θ(1) = Θ(log n)

Merge sort recursively handles two subproblems of half the size, then combines the results in linear time:

T(n) = 2T(n/2) + Θ(n) = Θ(n log n)

Temporarily counting each multiplication as one step, factorial recursion reduces n by one:

T(n) = T(n - 1) + Θ(1) = Θ(n)

These recurrences stop at constant-size inputs with Θ(1) base cost; rounding n/2 does not change these asymptotic results. Python factorial requires a separate bit-cost analysis for its growing integers. The non-recursive term must represent the actual work of the current call. If slicing copies k elements, it cannot be treated as Θ(1); if merging requires a linear scan, it's wrong to only count the recursive calls.

4. Time Tree and Call Stack Are Two Different Accounts

Time sums the work of every call. Stack space counts only calls that have not yet returned at the same moment. Visiting many nodes does not mean they all occupy the stack together.

For power-of-two n, merge sort has log₂ n levels of merging work, plus one leaf level, with each layer processing Θ(n) elements in total, so the overall time complexity is Θ(n log n). Yet at any given moment, only one recursive path is being followed, the depth of the call stack is Θ(log n). Additionally, merging buffers typically require another Θ(n) of auxiliary space.

Naive Fibonacci is different:

def fib(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Its call tree contains many redundant subproblems. Although the recursion depth is only Θ(n), the total number of function calls grows exponentially. If C(n) counts calls, C(n) = 2F(n + 1) − 1, where F is Fibonacci. Thus the tight bound is Θ(φⁿ), with φ = (1 + √5) / 2; O(2ⁿ) is a looser upper bound. Seeing two recursive branches does not justify Θ(2ⁿ); the shape of the tree depends on branch size, whether pruning is applied, and whether memoization is used.

5. Three Common Solution Approaches

Expansion

After expanding T(n) = T(n/2) + c k times, we obtain T(n/2ᵏ) + kc. Let n/2ᵏ = 1; then we derive k = log₂ n.

Recursion Tree

List the number of subproblems at each level and the amount of non-recursive work performed per subproblem, then sum over all levels. This method is especially effective at revealing structural patterns such as "each level has n" or "work grows layer by layer."

Substitution Method

First, make an educated guess about the asymptotic bound based on expansion or recursion tree analysis. Then verify the guess using mathematical induction to confirm that a constant exists. A guess is not a proof; substitution can expose overlooked lower-order terms and boundary conditions.

6. Master Theorem Applies Only to Fixed-Shape Recurrences

The classic form is:

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

Here a ≥ 1 and b > 1 are constants, subproblems shrink by the same ratio, f(n) is eventually non-negative, and constant-size base cases cost Θ(1). Set p = log_b a. These sufficient conditions come from a commonly used version; ε and k must be independent of n:

Relationship	Intuition	Typical Conclusion
f(n) = O(n^(p−ε)), ε > 0	Leaf/subproblem work dominates	Θ(n^p)
f(n) = Θ(n^p log^k n), k ≥ 0	Sum work over the levels	Θ(n^p log^(k+1) n)
f(n) = Ω(n^(p+ε)), ε > 0, and a·f(n/b) ≤ c·f(n) for some c < 1 and all sufficiently large n	Root work dominates; the latter inequality is the regularity condition	Θ(f(n))

Three examples:

8T(n/2) + Θ(n²)  -> Θ(n³)
2T(n/2) + Θ(n)   -> Θ(n log n)
2T(n/2) + Θ(n²)  -> Θ(n²)

Common cases where the theorem cannot be directly applied:

• T(n) = T(n - 1) + Θ(1): subproblems do not shrink by a fixed ratio;
• T(n) = T(n/3) + T(2n/3) + Θ(n): subproblems have different sizes;
• Naive Fibonacci: T(n-1) + T(n-2) + Θ(1);
• Branching factor or shrinking ratio changes with n.

Start with expansion, recursion trees, or substitution. Unequal but fixed-fraction subproblems such as T(n/3) + T(2n/3) may fit the Akra–Bazzi method when its conditions hold; it does not automatically cover n−1 recursion. Also, f(n) = n^p / log n is outside the table’s second case, which requires k ≥ 0.

7. Verify Recursion Intuition with Call Count

Save as recurrence_demo.py:

def fib_with_calls(n: int) -> tuple[int, int]:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n, 1
    left, left_calls = fib_with_calls(n - 1)
    right, right_calls = fib_with_calls(n - 2)
    return left + right, 1 + left_calls + right_calls

def merge_work(n: int) -> int:
    if n < 1 or n & (n - 1):
        raise ValueError("n must be a positive power of two")
    if n == 1:
        return 0
    return 2 * merge_work(n // 2) + n

def main() -> None:
    fib_value, fib_calls = fib_with_calls(10)
    sizes = [1, 2, 4, 8, 16]
    work = [merge_work(size) for size in sizes]

    assert fib_value == 55
    assert fib_calls == 177
    assert work == [size * (size.bit_length() - 1) for size in sizes]

    print(f"fib(10): {fib_value}")
    print(f"Naive Fibonacci call count: {fib_calls}")
    print(f"Merge-layer work: {dict(zip(sizes, work))}")
    print("Recurrence check passed")

if __name__ == "__main__":
    main()

python3 recurrence_demo.py

Expected output:

fib(10): 55
Naive Fibonacci call count: 177
Merge-layer work: {1: 0, 2: 2, 4: 8, 8: 24, 16: 64}
Recurrence check passed

fib_with_calls actually executes recursive calls and counts their nodes. merge_work only evaluates the work model: it doubles one subresult without sorting, scanning n elements, or making two recursive calls. Returning n log₂ n does not mean that helper itself takes Θ(n log n) time. These instances check formula values, not asymptotic proofs.

8. Amortized Cost Does Not Require Probability Distributions

When a dynamic array performs a push operation, most operations simply write to a single position. However, the operation that triggers capacity exhaustion requires allocating a larger array and copying all previous elements. Starting from empty and growing geometrically, the total number of element copies across the first n appends forms a geometric series, and the total cost remains Θ(n). Thus, the amortized cost per push is Θ(1).

This does not imply that the worst-case cost of each individual operation is constant, nor does it mean taking an average over random inputs. Amortized analysis examines the total cost of any valid sequence of operations, and three common perspectives are used:

• The aggregate method: Compute the total cost of the entire operation sequence first.
• The accounting method: Store "credit" from cheap operations to pay for future expensive ones.
• The potential method: Represent accumulated future work as a potential energy function of the current state.

9. Complexity and Benchmarking Answer Different Questions

Complexity analysis explains the trend in work required by a model as input size grows; benchmarking observes actual performance under a specific implementation, runtime, machine, and input distribution. Keep their roles separate:

• Complexity does not tell you about caching, vectorization, object layout, or constant factors;
• A single timing measurement cannot prove an asymptotic bound;
• On small inputs, a simple Θ(n²) implementation might outperform a more complex Θ(n log n) implementation with large constants;
• Engineering decisions should first eliminate any approach with clearly unsuitable growth behavior, then use representative workloads to measure candidate implementations.

Write a Complete Analysis

Pick any recursive function and clearly specify: input scale, cost model, recurrence relation, base cases, solution method, time upper and lower bounds, recursion stack space, and auxiliary space. If you apply the Master Theorem, provide step-by-step verification that each of a, b, f(n) satisfies the required conditions and that the theorem's applicability criteria are met.

Then modify the interface to return all results and verify whether the output size introduces a new lower bound. Finally, state whether the conclusion represents best-case, worst-case, average-case, expected-case, or amortized cost. These five labels must be treated as distinct and non-interchangeable.

Review Formal Definitions and Standard Algorithms

• MIT 6.006: Asymptotic Notation.
• Open Data Structures.
• Python Wiki: Time Complexity: Verify implementation assumptions when analyzing operations on Python containers.

Continue Learning: Continuous Grids and Node Paths

You now have three measuring tools: time, space, and output scale. The next chapter compares the contiguous storage of arrays with the node connections of linked lists, applying each analytical rule to operations such as access, insertion, deletion, and traversal.

Continue learning about arrays