1.3 Asymptotic Bounds, Recurrence Relations, and Amortized Analysis

After completing Common Complexity Analysis, spend about 45 minutes traversing the final level of the observation deck. Here, we formally distinguish O, Ω, and Θ, express recursive programs as recurrence relations, and clarify the boundaries where the Master Theorem applies and where it does not.

"No More Than" on a Map Isn't Enough

The first two vantage points taught you how to define input scale, count model operations, and express them in loop bounds. Master Chen unfolds three maps at the final level: the first marks only "not longer than this path," the second labels only "must go at least this far," and the third specifies both upper and lower bounds.

All three maps can be correct, yet they answer different questions. If a linear scan can be written as O(n²) or O(2ⁿ), a single loose upper bound isn't sufficient to determine its actual growth rate.

1. O, Ω, and Θ are boundaries, not input scenarios

Let f(n) be a non-negative cost function under a chosen cost model.

• 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 requirement is changed to return only the count, an iterator, or a compressed representation.

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

The paths in the algorithm forest begin to split. As you reach each node, you break the problem into several smaller subproblems, and must also account for the cost of organizing and combining the results. Focusing only on a single loop will miss the entire call tree. Instead, start by writing out the recurrence relation that captures "how many branches," "how large each branch is," and "what work this layer actually performs."

In binary search, the recursion proceeds to just half the interval, with constant overhead:

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)

For factorial recursion, each call reduces n by one:

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

The non-recursive term in the recurrence must represent the actual work performed by 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

Master Chen placed two notebooks beside the map: one tracking the total distance walked across the entire forest, and the other recording only how many unreturned paths are currently stacked in the backpack. The first reflects total work done; the second corresponds precisely to the recursive call stack.

The recursion tree of merge sort has log₂ n layers, 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 < 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. When you encounter two recursive branches, you cannot simply write Θ(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)

where a ≥ 1 and b > 1 are constants, and all subproblem sizes are equal. First compare f(n) and n^(log_b a).

Relationship	Intuition	Typical Conclusion
f(n) is polynomially smaller	Leaf/subproblem work dominates	Θ(n^(log_b a))
f(n) are of the same order, possibly differing by a logarithmic factor	Work across levels is nearly balanced	An additional logarithmic factor
f(n) is polynomially larger and satisfies the regularity condition	Root-level non-recursive work dominates	Θ(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.

In such cases, techniques like expansion, recursion tree analysis, substitution, or the more general Akra–Bazzi method are appropriate. The conditions under which the Master Theorem applies are more important than memorizing the three cases.

7. Verify Recursion Intuition with Call Count

Save as recurrence_demo.py:

from math import log2


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 == [int(size * log2(size)) for size in sizes]

    print(f"fib(10): {fib_value}")
    print(f"Plainness Fibonacci Call count:{fib_calls}")
    print(f"Merge layer operation:{dict(zip(sizes, work))}")
    print("Recursive formula 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 relation passes verification

The counting program only verifies that specific instances match the derived formulas, it does not replace asymptotic proofs. Its value is in turning the abstract "number of nodes" and "work per layer" in a recursion tree into concrete, checkable data.

8. Amortized Cost Does Not Require Probability Distributions

In the forest, a stretchable bridge adds just one plank at a time under normal use. But when capacity is exhausted, the entire bridge must be moved to a larger foundation. A single expensive expansion doesn't mean every step was costly, instead, the total cost of a sequence of deterministic operations can be spread evenly across each individual operation.

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. If capacity grows geometrically, the total number of element copies across the first n pushes 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. Both require:

• 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.

Before Leaving the Observation Deck, 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: Analysis of Algorithms.
• Python Wiki: Time Complexity: Verify implementation assumptions when analyzing operations on Python containers.

Next Stop: 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