Counting the work: from recurrences to big O

Every big-O on this site came from a count. The sorting article says merge sort is $O(n \log n)$, but it skips the arithmetic behind that log: split in half, sort each half, then merge. This article does the count. A recursive algorithm has a running time that refers to itself. That function is a recurrence. Read the recurrence carefully and it gives you a big-O bound through a small, mechanical rule: the master method. The real skill is knowing where the work lives. It is the same sum-a-recursion habit from the site’s Induction article. Learn the count first. Use the shortcut second.

A recurrence is a work count

A recursive algorithm does two kinds of work: its recursive calls, and its own work before and after those calls—the split and the combine. Write both down and you have a recurrence. Let $T(n)$ be the running time on an input of size $n$. Most divide-and-conquer algorithms fit this shape:

$$T(n) \le a \cdot T(n/b) + O(n^d)$$

Three parameters carry the information. $a$ is the number of recursive calls. $b$ is the factor that shrinks each input. $d$ is the exponent in the combine step’s cost. Roughgarden’s Algorithms Illuminated calls this the “standard recurrence” and names the three parameters: $a$, “the number of recursive calls”; $b$, “the input size shrinkage factor”; $d$, “the exponent in running time of the ‘combine step’.” Those three parameters are the entire input to the master method. Plug in $a$, $b$, and $d$, and it returns a bound. The book calls it “a ‘black-box’ method for determining the running time of recursive algorithms - plug in a few key characteristics of the algorithm, and out pops an upper bound on the algorithm’s running time.”roughgarden

Count the work first.

The recursion tree: where the work lives

Unroll the recursion into a tree. The root does $O(n^d)$ combine work and creates $a$ children, each with a problem of size $n/b$. Each child does $O((n/b)^d)$ work and creates $a$ grandchildren. At level $j$, there are $a^j$ subproblems, each of size $n/b^j$. Multiply those two quantities by the work per subproblem, and the total becomes:

$$c \cdot n^d \cdot \left(\frac{a}{b^d}\right)^j$$

Sum that expression across the tree’s $\log_b n$ levels. The master method is already in the ratio $a/b^d$, raised to $j$. A geometric series has three possible shapes. Those are the three cases:

defmodule Count do
  # Level j of a standard recurrence does c * n^d * (a / b^d)^j work
  # (c = 1 here; it washes out of the comparison).
  def level_work(n, a, b, d, j) do
    :math.pow(n, d) * :math.pow(a / :math.pow(b, d), j)
  end

  def levels(n, b), do: round(:math.log(n) / :math.log(b))

  def trace(name, n, a, b, d) do
    IO.puts(name)
    for j <- 0..levels(n, b) do
      IO.puts("  level #{j}: #{Float.round(level_work(n, a, b, d, j), 1)}")
    end
  end
end

Count.trace("Merge sort   (a=2, b=2, d=1): flat", 256, 2, 2, 1)
Count.trace("Karatsuba    (a=3, b=2, d=1): rising", 256, 3, 2, 1)
Count.trace("One call, linear combine (a=1, b=2, d=1): falling", 256, 1, 2, 1)

The output gives the work at each level for three recurrences. Merge sort stays flat at 256 because $a = b^d$, so the ratio is $1$. The work neither grows nor shrinks. Karatsuba rises from 256 to 6561 because $a = 3$ is larger than $b^d = 2$. A recurrence with one recursive call and a linear combine falls from 256 to 1 because the combine work outweighs the branching. Roughgarden calls this comparison “a tug-of-war”: $a$ measures subproblem proliferation, while $b^d$ measures work shrinkage. The result is a draw, a win for shrinking, or a win for proliferation.

The master method: three outcomes

The three shapes produce three bounds. Compare $a$ with $b^d$:

Compare	Work shape	Bound
$a < b^d$	shrinks down the tree, root dominates	$O(n^d)$
$a = b^d$	flat, $\log_b n$ levels of it	$O(n^d \log n)$
$a > b^d$	grows down the tree, leaves dominate	$O(n^{\log_b a})$

That is the rule. Roughgarden states it as Theorem 4.1: if $T(n)$ is defined by a standard recurrence with $a \ge 1$, $b > 1$, and $d \ge 0$, then the bound is $O(n^d \log n)$ when $a = b^d$, $O(n^d)$ when $a < b^d$, and $O(n^{\log_b a})$ when $a > b^d$.roughgarden These are not three separate rules. They are three outcomes of one comparison. The winning level of the tree pays for the result.

Merge sort, counted

Apply the method to the site’s Merge Sort problem. Split the list in half, sort both halves, and merge them. That gives two recursive calls ($a = 2$), each on half the input ($b = 2$), plus a merge step that walks both halves once ($d = 1$). The recurrence is $T(n) \le 2 \cdot T(n/2) + O(n)$. Compare $a = 2$ with $b^d = 2^1 = 2$. Since $a = b^d$, this is the flat case, and the answer is $O(n^d \log n) = O(n \log n)$. The problem’s instruction to “aim for $O(n \log n)$” is this arithmetic in one sentence.

Binary search has the same balanced case in a different form. It makes one call on half the input ($a = 1$, $b = 2$) and does constant work to choose that half ($d = 0$). Thus $a = 1 = 2^0 = b^d$. It is still the flat case, with bound $O(n^0 \log n) = O(\log n)$. The What a comparison is worth article derives that log from first principles. Here, the recurrence gives the same log directly. The binary trees article shows where it lives: the recursion tree is a tree, and the log is its height.

The leaf-heavy case: Karatsuba

Remember the third case. It explains why divide-and-conquer can help. Karatsuba’s integer-multiplication algorithm saves one of four recursive calls with a trick, leaving $a = 3$, $b = 2$, $d = 1$. Now $a = 3 > 2 = b^d$, so this is the leaf-heavy case. The bound is $O(n^{\log_2 3}) = O(n^{1.59})$. A fractional exponent—$n$ to the $1.59$—describes a real running time: asymptotically faster than the grade-school $O(n^2)$, but slower than linear. Roughgarden says that saving a recursive call “leads to a fundamentally better running time, and the integer multiplication algorithm that you learned in the third grade is not the fastest possible.”roughgarden The tree explains the result. When $a > b^d$, deeper levels do more work than shallow ones, and there are $n^{\log_b a}$ leaves to pay for.

Two recurrences, two counts: maximum subarray

The site’s Maximum Subarray gives a clean example of a recurrence as a design decision. Count it before you code. The textbook divide-and-conquer solution splits the array in half. The best subarray is entirely in the left half, entirely in the right half, or crosses the midpoint. Compute the crossing case by scanning left and right from the middle in linear time. This is the same recurrence as merge sort, $T(n) \le 2 \cdot T(n/2) + O(n)$, so the master method gives $O(n \log n)$.

The site’s reference solution uses a different recurrence—or, more precisely, no recurrence. Kadane’s algorithm makes one pass, carrying a running current sum and the best seen. It uses a fold, not recursion, and its count is $O(n)$. Count before you write the code and the choice is clear: divide-and-conquer is worse here. That is why the problem is filed under dynamic programming rather than divide-and-conquer. The dynamic programming article covers the other side of that decision. It keeps the recursion but caches the answers, so the cached recurrence requires different arithmetic.

What the master method will not do

The shortcut has two limits. It reads only standard recurrences, where every recursive call uses a subproblem of the same size. An algorithm that recurses once on the first third of an input and once on the rest produces a non-standard recurrence, which the method does not cover; Roughgarden states this restriction explicitly. The master method also returns an upper bound, not an exact count. It drops the constants and assumes the base case is small. Those are the caveats the What O(n) actually promises article attaches to every big-O claim.

The proof matters because it uses the site’s own subject. Total work is a sum over $\log_b n$ levels. The three cases come from summing a geometric series: bound the whole by the sum of its parts, then bound each part with a level-counting argument. That is induction with a summation symbol. It is the same argument the Induction article teaches through the site’s own recursion exercises.

Where to go next

• Merge Sort - write the algorithm whose recurrence this article counted; the merge step is the $O(n)$ combine.
• Maximum Subarray - the problem with two recurrences; Kadane’s linear count beats the $O(n \log n)$ divide-and-conquer count.
• What O(n) actually promises - the growth-shape vocabulary this article’s bounds are written in.
• Sorting: the wall at n log n - the $O(n \log n)$ this article derived, and where the log comes from.
• What a comparison is worth
  • binary search’s $O(\log n)$, the balanced case with $d = 0$.
• Binary trees: where the log lives
  • the recursion tree is a tree; the log is its height.
• Induction - the proof shape underneath the master method’s level-summing argument.

The master method is a shortcut. Keep the skill it replaces: counting the work. Before you write a recursive algorithm, write its recurrence—how many calls, how much smaller, and how expensive the combine is—then compare $a$ with $b^d$. That comparison tells you whether the work shrinks, stays flat, or grows as the recursion deepens. It gives you the big-O without running a line of code. Counting the work is the technique. The master method is the part you memorize.