Mathematical Foundations for Algorithm Analysis

Mathematical Foundations for Algorithm Analysis

Introduction: The Language of Efficiency

When we examine the performance of an algorithm, we quickly discover that the actual running time depends on factors far beyond the algorithm's design itself. The hardware executing the code, the compiler optimizing the implementation, the characteristics of the input data, and numerous other environmental factors all contribute to the measured performance. Yet despite this complexity, we need a way to reason about algorithms in a manner that is both rigorous and practical—a framework that lets us compare algorithms independent of implementation details and predict their behavior as problem sizes grow. This framework is built upon mathematical foundations that transform the question of "which algorithm is faster" from an empirical measurement into a provable property of the algorithm itself.

The mathematical tools we develop in this chapter serve as the vocabulary and grammar of algorithm analysis. Without these tools, we can observe that one algorithm feels faster than another on small inputs, but we cannot articulate why it will continue to perform better as problems scale to sizes encountered in real applications. With these tools, we can prove statements like "merge sort runs in $O(n \log n)$ time" and understand precisely what that claim means, what assumptions underlie it, and how it guides our choice of algorithms in practice.

Our journey through these foundations begins with asymptotic notation—the mathematical formalism that captures the idea of growth rates. We then examine the techniques for solving recurrence relations, which arise naturally when we analyze recursive algorithms. We explore summations and their applications, study combinatorial principles for counting operations, and develop probability theory for understanding randomized algorithms. Finally, we introduce amortized analysis, a powerful technique for analyzing sequences of operations where the total cost, spread across many operations, yields insights invisible in single-operation analysis. By the chapter's conclusion, you will possess the complete toolkit for rigorous algorithm analysis, understanding not merely how to apply these techniques but why they work and when to deploy each one.

Asymptotic Notation: Measuring Growth

The Intuition Behind Asymptotics

Consider two functions describing the running times of algorithms. The first algorithm runs in $f(n) = 100n + 500$ microseconds, while the second runs in $g(n) = n^2/100 + 10000$ microseconds. For small values of $n$, the comparison is ambiguous—the constant terms and lower-order terms can dominate. But as $n$ grows large, a clear pattern emerges. When $n = 1000$, the first algorithm takes approximately $100 \times 1000 = 100000$ microseconds while the second takes approximately $1000^2/100 = 10000$ microseconds. When $n = 100000$, the first algorithm takes $10^7$ microseconds while the second takes $10^{10}/100 = 10^8$ microseconds. The first algorithm, despite its larger coefficient on $n$, eventually dominates because it grows linearly while the second grows quadratically.

This observation—that for sufficiently large inputs, the behavior of a function is determined by its rate of growth rather than constant factors or lower-order terms—forms the intuition behind asymptotic notation. We say that an algorithm with running time $\Theta(n^2)$ grows faster than one with running time $\Theta(n \log n)$, which grows faster than one with running time $\Theta(n)$. The constant factors and lower-order terms, while important for fine-grained performance tuning, do not affect this classification.

Big-O Notation: Upper Bounds

The most commonly used asymptotic notation in algorithm analysis is Big-O notation, which provides an upper bound on the growth rate of a function. We write $f(n) = O(g(n))$ when there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$, we have $0 \leq f(n) \leq c \cdot g(n)$. In this case, we say that $g(n)$ is an asymptotic upper bound for $f(n)$.

The formal definition requires careful attention to each component. The inequality $0 \leq f(n)$ establishes that we are dealing with non-negative functions, which is appropriate for running times and other quantities that cannot be negative. The inequality $f(n) \leq c \cdot g(n)$ captures the essence of an upper bound: beyond some point $n_0$, the function $f(n)$ never exceeds $c$ times $g(n)$. The constant $c$ cannot depend on $n$, which prevents us from "absorbing" $f(n)$ into $g(n)$ by making $c$ grow with $n$.

To solidify this definition, consider $f(n) = 5n^2 + 3n + 7$. We can establish several Big-O bounds. Clearly, $f(n) = O(n^2)$, with $c = 6$ and $n_0 = 1$, since $5n^2 + 3n + 7 \leq 6n^2$ for all $n \geq 1$. More loosely, we also have $f(n) = O(n^3)$, since $5n^2 + 3n + 7 \leq n^3$ for all $n \geq 6$. The tighter bound $O(n^2)$ is more informative, but both are technically correct. This illustrates an important convention: when we write $f(n) = O(g(n))$, we typically intend $g(n)$ to be the tightest reasonable bound, though technically any asymptotically larger function also qualifies.

The definition of Big-O is sometimes written with absolute values or with $\leq$ instead of $<$, but these variations are equivalent for the purposes of algorithm analysis. The key insight is that Big-O captures the notion of "grows no faster than"—a function in $O(g(n))$ cannot eventually grow faster than some constant multiple of $g(n)$.

Big-Ω Notation: Lower Bounds

If Big-O provides an upper bound, Big-Ω provides a symmetric lower bound. We write $f(n) = \Omega(g(n))$ when there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$, we have $0 \leq c \cdot g(n) \leq f(n)$. Here, $g(n)$ is an asymptotic lower bound for $f(n)$—beyond $n_0$, the function $f(n)$ is always at least $c$ times $g(n)$.

For the same function $f(n) = 5n^2 + 3n + 7$, we have $f(n) = \Omega(n^2)$, taking $c = 5$ and $n_0 = 1$, since $5n^2 \leq 5n^2 + 3n + 7$ for all $n$. We also have $f(n) = \Omega(n)$, since $n \leq 5n^2 + 3n + 7$ for all $n \geq 1$. The bound $\Omega(n^2)$ is tighter and more useful.

Big-Ω captures the notion of "grows at least as fast as"—a function in $\Omega(g(n))$ eventually grows at least proportionally to $g(n)$. This is essential for proving lower bounds on problems, where we want to show that no algorithm can possibly be faster than a certain rate. If we can prove that any algorithm solving a particular problem requires $\Omega(n \log n)$ comparisons, then we know that algorithms running in $O(n)$ time cannot exist for that problem.

Big-Θ Notation: Tight Bounds

When a function is bounded both above and below by the same asymptotic order, we have a tight bound, expressed with Big-Θ notation. We write $f(n) = \Theta(g(n))$ when there exist positive constants $c_1$, $c_2$, and $n_0$ such that for all $n \geq n_0$, we have $0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$. In other words, $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

The function $f(n) = 5n^2 + 3n + 7$ is $\Theta(n^2)$. We have already established both $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$. This tight bound captures the true order of growth—neither larger nor smaller asymptotically.

Big-Θ is particularly valuable when we want to precisely characterize an algorithm's complexity. When we say merge sort runs in $\Theta(n \log n)$ time, we mean precisely that the running time grows proportionally to $n \log n$ for large $n$. We cannot improve this characterization by using $O(n \log n)$ (which would be less precise) or by using $\Omega(n \log n)$ (which alone gives only a lower bound). The tight bound $\Theta(n \log n)$ is the most informative statement.

Alternative Notations: Little-o and Little-ω

Beyond the "equivalence" relations of Big-O, Big-Ω, and Big-Θ, there are also "strict" asymptotic n