Foundations of Algorithm Analysis

When we examine the history of computing, a pattern emerges that consistently surprises newcomers to the field: the difference between a fast algorithm and a slow one is not merely a matter of degree—it is a matter of feasibility. Problems that appear identical in their input-output behavior can have solutions ranging from those that complete in milliseconds to those that would require longer than the age of the universe to finish. This is not hyperbole. Consider a problem as fundamental as sorting a million numbers. A well-designed algorithm accomplishes this task in roughly twenty million operations, finishing in a fraction of a second on any modern machine. An algorithm with quadratic complexity, by contrast, would require approximately one trillion operations—a difference of five orders of magnitude. Understanding why this distinction exists, and developing the mathematical framework to reason precisely about such differences, is the central purpose of this chapter.

Algorithmic efficiency is the study of how the resources consumed by an algorithm—most notably time and memory—scale with the size of the input. Before we can compare algorithms, optimize solutions, or reason about practical performance, we must establish a shared vocabulary and a rigorous mathematical foundation. This chapter constructs that foundation from the ground up. We begin by clarifying the relationship between correctness and efficiency, two properties that are both essential and independent. We then introduce asymptotic notation as a precise language for characterizing running times, examining each variant—Big O, Big Omega, and Big Theta—in both its mathematical definition and its practical interpretation. With these tools in hand, we analyze both iterative and recursive algorithms, learning to count operations systematically and to solve recurrence relations using the Master Theorem. We devote careful attention to the distinction between worst-case, average-case, and best-case analysis, understanding not just how to compute these quantities but when each perspective is the appropriate one to adopt. Throughout, we connect theoretical results to concrete performance expectations, ensuring that the mathematics we develop remains anchored in practical reality.

Correctness and Efficiency: Two Independent Dimensions

A common misconception among students new to algorithm design is that an algorithm is either correct or incorrect, and that efficiency is a secondary concern addressed through optimization after correctness is achieved. This view, while understandable, fundamentally mischaracterizes the relationship between these two properties.

An algorithm is correct if it produces the right answer for every valid input. This is a binary property in theory—an algorithm either satisfies its specification or it does not. Efficiency, on the other hand, describes how well an algorithm uses computational resources. These two properties are orthogonal: a correct algorithm can be prohibitively slow, and an efficient algorithm can produce incorrect results.

Consider the problem of computing the greatest common divisor (GCD) of two positive integers. The Euclidean algorithm, developed over two millennia ago, computes $\gcd(a, b)$ through a sequence of division steps, running in $O(\log \min(a, b))$ time. It is both correct and efficient. An alternative approach might simply try all integers from $1$ to $\min(a, b)$ and select the largest that divides both—this brute-force method is correct, but its running time is $O(\min(a, b))$, which is exponentially slower in the magnitude of the inputs compared to Euclidean algorithm. Both algorithms are correct; only one is efficient.

More dramatically, consider the problem of finding a Hamiltonian cycle in an undirected graph—a path that visits every vertex exactly once. A brute-force search that examines every possible permutation of vertices runs in $O(n!)$ time, where $n$ is the number of vertices. For a graph with just 20 vertices, this would require examining more than $2.4 \times 10^{18}$ permutations. No amount of hardware optimization or low-level coding makes this approach practical. The same problem with an efficient algorithm, when one exists, would run in polynomial time. The efficiency gap is not a constant factor—it is a qualitative difference between problems that are tractable and those that are not.

This distinction motivates our entire enterprise. Correctness establishes whether an algorithm deserves to exist; efficiency determines whether it can actually be used. An algorithm that cannot finish within a reasonable timeframe is, for practical purposes, no algorithm at all.

Input Size and Resource Consumption

Before we can analyze how an algorithm's resource consumption scales, we must first establish what we mean by "input size." The input size, typically denoted $n$, is a measure of the quantity of data presented to the algorithm. The appropriate measure depends on the problem domain.

For sorting or searching problems, $n$ typically represents the number of elements in the input collection. For graph algorithms, $n$ may represent the number of vertices and $m$ the number of edges. For numerical algorithms involving integers, the input size is often measured in bits—the number of bits required to represent the largest input value. For matrix operations, $n$ might represent the dimension of the matrix.

This distinction is not merely pedantic. It has profound implications. Consider the problem of testing whether an integer $N$ is prime. If we measure input size as the magnitude of $N$ (the integer value itself), then a trivial algorithm that runs in $O(\sqrt{N})$ time appears nearly linear. But if we measure input size correctly as the number of bits $b = \lceil \log_2(N+1) \rceil$ required to represent $N$, then $\sqrt{N} = 2^{b/2}$ is exponential in the input size. These two perspectives lead to completely different conclusions about algorithmic efficiency, and the bit-length measure is the one that matters for cryptographic applications where we work with thousand-bit integers.

Once we have established a measure of input size, we can characterize an algorithm's resource consumption as a function $f(n)$ that maps input size to resource usage. The fundamental question becomes: how does $f(n)$ behave as $n$ grows without bound? This is where asymptotic notation provides its essential service.

Asymptotic Notation: The Language of Growth Rates

Asymptotic notation describes the behavior of functions as their arguments grow large. Rather than providing an exact count of operations, which depends on countless implementation details, constant factors, and hardware characteristics, asymptotic notation captures the fundamental rate of growth. This abstraction is powerful precisely because it strips away the incidental and reveals the essential.

Big O Notation: Upper Bounds

Big O notation, denoted $O(f(n))$, describes an upper bound on the growth rate of a function. We say that $T(n) = O(f(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$, we have $T(n) \leq c \cdot f(n)$.

Formally, let $T(n)$ and $f(n)$ be functions from positive integers to non-negative real numbers. We define:

$$T(n) = O(f(n)) \iff \exists c > 0, \; n_0 > 0 \; \text{such that} \; \forall n \geq n_0, \; T(n) \leq c \cdot f(n)$$

The intuition behind this definition is straightforward: beyond some input size $n_0$, the function $T(n)$ never grows faster than a constant multiple of $f(n)$. The constants $c$ and $n_0$ are not part of the notation—they can be any positive values that satisfy the condition. Big O gives us a ceiling on performance.

Consider the function $T(n) = 3n^2 + 5n + 2$. We can say that $T(n) = O(n^2)$. Indeed, for $n \geq 1$, we have $3n^2 + 5n + 2 \leq 3n^2 + 5n^2 + 2n^2 = 10n^2$, so $c = 10$ and $n_0 = 1$ suffice. We could also say $T(n) = O(n^3)$ or $T(n) = O(2^n)$, but these are weaker,