Algorithm Analysis and Growth Rates

Overview

Algorithm analysis is the study of how the resources an algorithm consumes — almost always running time, sometimes memory — scale as the input size n grows, independent of any particular machine or programming language. Rather than timing an implementation with a stopwatch, analysis counts the number of elementary operations (comparisons, arithmetic operations, array accesses) as a function of n, then classifies that function by its growth rate using big-O notation, which discards constant factors and lower-order terms because those become irrelevant for large n. This lets two very different algorithms for the same problem be compared abstractly: an O(n²) sort and an O(n log n) sort will eventually diverge no matter how the constants compare, because n log n grows strictly slower than n² once n is large enough. Analyzing algorithms that call themselves recursively (like merge sort or binary search) typically produces a recurrence relation for the running time, which is then solved — often via the Master Theorem — to obtain a closed-form growth rate.

Intuition

Growth-rate analysis is about the shape of a curve, not any single data point on it: a slow constant multiplied onto a fast-growing shape will still eventually be overtaken by a fast constant multiplied onto a slow-growing shape, once n is big enough. Picture an O(n²) algorithm and an O(n log n) algorithm racing as n climbs — even if the O(n²) algorithm starts faster for small n because of favorable constants, the quadratic curve bends upward much more sharply, so there is always a crossover point past which the n log n algorithm wins and never loses again. The Master Theorem formalizes a three-way tug-of-war inside a recursive algorithm: the work done by the recursive calls themselves (captured by n^(log_b a)) versus the work done combining their results (f(n)) — whichever one grows faster dominates the total running time, and a tie adds one extra log n factor.

Formal Definition

Definition

The running time of an algorithm is a function T(n) of input size n. Divide-and-conquer algorithms that split a problem of size n into a subproblems of size n/b, doing f(n) extra work per split, satisfy a recurrence solved by the Master Theorem:

T(n) = a\, T(n/b) + f(n), \qquad a \ge 1,\ b > 1

Divide-and-conquer recurrence

\text{If } f(n) = O(n^{\log_b a - \epsilon}) \text{ for some } \epsilon > 0, \text{ then } T(n) = \Theta(n^{\log_b a})

Master Theorem, case 1 (splitting dominates)

\text{If } f(n) = \Theta(n^{\log_b a}), \text{ then } T(n) = \Theta(n^{\log_b a} \log n)

Master Theorem, case 2 (balanced)

\text{If } f(n) = \Omega(n^{\log_b a + \epsilon}) \text{ for some } \epsilon > 0 \text{ (and a regularity condition holds), then } T(n) = \Theta(f(n))

Master Theorem, case 3 (merging dominates)

Worked Examples

Evaluate both functions at n = 10.
$f(10) = 100, \quad g(10) = 500$
Evaluate both functions at n = 100.
$f(100) = 10000, \quad g(100) = 5000$

Answer: At n=10, 50n (500) is larger than n² (100); at n=100, n² (10000) has overtaken 50n (5000) — illustrating that O(n²) eventually dominates O(n) despite a large constant, once n is large enough.

Practice Problems

Difficulty 4/10

Solve T(n) = 4T(n/2) + n using the Master Theorem.

Difficulty 5/10

Solve T(n) = 3T(n/4) + n² using the Master Theorem.

Difficulty 6/10

An algorithm A runs in exactly 200n operations, and algorithm B runs in exactly 2n² operations. For what values of n does algorithm A perform fewer operations than algorithm B?

Quiz

Summary

Algorithm analysis counts elementary operations as a function of input size n, then classifies growth with big-O notation.
Growth-rate comparisons hold only asymptotically: a faster-growing function eventually dominates regardless of constants.
Divide-and-conquer running times satisfy T(n) = aT(n/b) + f(n), solved by the Master Theorem.
The Master Theorem compares f(n) against n^(log_b a): whichever grows faster dominates; a tie adds a log n factor.
Merge sort's recurrence T(n) = 2T(n/2) + n solves to Θ(n log n) via the Master Theorem's balanced case.