Count work and solve recurrences

Prerequisites: Loops, logarithms, induction, and summation notation.

Learning objectives

• Derive a bound from a loop or recurrence.
• Distinguish a tight bound from an upper bound.
• Explain the assumptions behind an operation count.

Choose the quantity being measured

Let n be the number of input records. A running-time claim must name which operations count as constant cost. Comparing fixed-width integers is one model; comparing arbitrarily long strings is another. Big O gives an eventual upper bound up to a constant factor. Theta gives matching upper and lower bounds. Saying an algorithm is O(n²) does not establish that its growth is actually quadratic, because a linear function is also O(n²).

Count a triangular nested loop that visits all pairs with 0≤j<i<n. The inner body executes 0+1+…+(n−1)=n(n−1)/2 times. This is Theta(n²), even though the loop never visits half the square. By contrast, if an inner variable starts at 1 and doubles until it exceeds n, that loop performs floor(log₂n)+1 iterations. Nest it inside n independent outer iterations and the total is Theta(n log n).

A recurrence encodes the decomposition

Suppose a procedure splits n records into two equal groups, recursively processes both, and combines them using n primitive steps. For powers of two, write T(n)=2T(n/2)+n and T(1)=1. At depth i there are 2^i subproblems, each contributing n/2^i combine work, so every non-leaf level contributes n. There are log₂n such levels, followed by n leaves. Therefore T(n)=n log₂n+n under this exact cost model.

If the combine work were constant, the same recursion tree would have total Theta(n) work. If only one half were recursively processed, T(n)=T(n/2)+n would sum n+n/2+n/4+… and also be Theta(n). The number of children and work at each node are independent decisions; do not infer a recurrence from the visual shape of recursive code alone.

Bound the whole resource requirement

A time recurrence does not automatically describe memory. A depth-first implementation can reuse temporary space after a child returns. Two recursive calls appearing in the source do not imply that both stacks coexist. Conversely, retaining all intermediate arrays can consume much more memory than the call stack itself. State whether input storage, output storage, and auxiliary space are included.

Treat a derivation as a falsifiable account of the implementation. Identify where comparisons, allocation, copying, and arithmetic occur. Measure representative sizes after deriving the model, then investigate discrepancies. A cache transition can change constants; an accidental copy inside every iteration can change the asymptotic bound. Read the MIT recurrence and sorting notes, then explain which assumptions are needed for their analysis to apply to your own program.

Practice problem

Analyze these three expressions for n=2^k: A(n)=A(n/2)+3 with A(1)=2; B(n)=2B(n/2)+n with B(1)=1; and the loop that, for each i from 1 through n, runs a body i times. Give an exact formula under these models, a Theta bound, and the value at n=8. State one change to the implementation that would invalidate each cost model.

Worked solution

A(n)=2+3log₂n, so A(8)=11 and the bound is Theta(log n). The recursion-tree derivation gives B(n)=nlog₂n+n, so B(8)=32 and the bound is Theta(nlog n). The triangular loop totals n(n+1)/2, so it runs 36 times at n=8 and is Theta(n²). Copying the entire current input before the single recursive call changes A’s recurrence. Using a quadratic combine step changes B’s recurrence. Running the inner body on variable-length strings can invalidate constant-cost iteration in the final loop. These formulas are exact only for the stated base cases and counting conventions.

Check your understanding

Which recurrence has Theta(n) total work for powers of two?

• T(n)=T(n−1)+n
• T(n)=2T(n−1)+1
• T(n)=T(n/2)+n
• T(n)=2T(n/2)+n

Explanation

The geometric series n+n/2+n/4+… is bounded above by 2n and below by n.

A procedure has a proven O(n²) upper bound. Which conclusion is justified?

• Its running time is necessarily Theta(n²).
• Its running time must double when n doubles.
• Its memory use is O(n²).
• A linear running time remains compatible with that bound.

Explanation

An upper bound need not be tight and says nothing by itself about a separate resource such as memory.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →