Counting a finite collection and analyzing an algorithm both require an honest account of repetition. A committee can be counted several times by listing its members in different orders. A recursive program can solve the same mathematical subproblem several times through different calls. Dividing a count by a symmetry factor and sharing repeated subproblems are different repairs, but each starts by identifying exactly what the computation treats as a distinct object.
Motivation
Suppose eight students are available for three positions. If the positions are chair, secretary and treasurer, assigning three different students gives an ordered choice. If we are simply forming a three-person committee, permuting its members does not create another committee. Both questions involve the same people and the same number three; their answers differ because their objects differ.
An algorithmic counting question should likewise specify whether its objects are functions, subsets, strings or executions. If a hash function sends eleven keys into four buckets, a collision is unavoidable. This does not mean that every bucket has the same size, that some particular pair collides, or that the hash function is badly implemented. A counting bound proves only what its quantifiers say.
Recurrences create another opportunity to overcount or undercount. Merge sort makes two recursive calls of half the original size; binary search continues into only one half. The depths are similar, but the work per level differs. Drawing a recursion tree and summing its levels makes that distinction visible and explains when a logarithmic depth produces a logarithmic, linear or larger total cost.
Definitions
Definition 1.3.1
(Functions and their types)
A function assigns exactly one element of its codomain to each element of its domain . It is injective if equal outputs imply equal inputs, surjective if every codomain element occurs as an output, and bijective if both hold. The image can be smaller than the specified codomain. Changing the codomain while retaining the same assignment can change whether the function is surjective.
Definition 1.3.2
(Factorials and binomial coefficients)
For a nonnegative integer , define , with . For integers , write for the number of -element subsets of an -element set. For , that count is zero and we set ; the factorial formula below is used only when . An ordered list of distinct elements remembers its first, second and later entries; an -element subset remembers only membership. Sampling with replacement permits repeated elements, so its lists are different objects again.
Definition 1.3.3
(Asymptotic notation)
For eventually nonnegative functions on the positive integers, means there are constants and such that for every . Write when , and when both bounds hold. The constants do not depend on . These are eventual comparisons, so finitely many small inputs can be handled separately. Logarithms with different fixed bases greater than one differ by a constant factor for such bounds.
Definition 1.3.4
(Recurrences and recursion trees)
A recurrence specifies a function through smaller arguments together with base values. For a cost recurrence, each term must correspond to a particular part of the algorithm: recursive calls, combination work or initialization. A recursion tree is an accounting device whose nodes are call occurrences. Two nodes can have equal input values and still represent two executions if the program makes both calls without memoization.
Theorem/proposition
Theorem 1.3.5
(Ordered assignments and subsets)
If and , with , the number of injections from to is , and
There is exactly one function from the empty set to any fixed set. For , all functions from an -element set to an -element set are counted by ; if , that count is zero.
Theorem 1.3.6
(Pigeonholes give a lower bound on a largest fiber)
If objects are assigned to boxes, then at least one box receives at least objects. In particular, no function from a finite set of larger cardinality to a smaller one can be injective.
Theorem 1.3.7
(A balanced recurrence from its level sum)
Let , where , and suppose and for larger such inputs, with constants , and . Then, as powers of two grow,
These conclusions concern the stated balanced recurrence. Unequal subproblem sizes or extra non-polynomial work require a new analysis.
Proof sketch or proof idea
Proof
(Counting injections and subsets)
To count injections, list the domain elements in a fixed order. The first has possible images, the next , and the th has , because injectivity forbids the previous images. Their product is . For the product is empty and equals one, reflecting the unique empty assignment. If repetition is allowed, every domain element has choices, giving for .
Every ordered list of distinct elements determines an -element subset by forgetting order. Each such subset has exactly orderings, so the fibers of this forgetting map all have size . Partitioning the ordered lists by their underlying subsets and dividing by that common fiber size proves the binomial formula. The equal fiber size is the justification for division; one cannot generally divide a count by a convenient number when different objects have different numbers of descriptions.
Proof
(The pigeonhole bound)
For the pigeonhole bound, put . If every box contained at most objects, the total would be at most , by the defining property . This contradicts the total number of objects. The case is harmless: every box contains zero, which meets the claimed lower bound zero. When , the bound gives at least two in some box, contradicting injectivity.
Proof
(Summing a balanced recurrence by levels)
For the recurrence, the tree has height . At level , there are nodes, each of size , so their total nonrecursive work is . There are leaves, of cost each. When is an integer this is literally a call tree; for a noninteger the same expansion is an algebraic identity. In either interpretation,
Set . If , the geometric sum is between one and for . The leaf term is , so the total is . If , the sum is and the leaf term is ; since , the total is for growing .
If , the sum is for large . Multiplying by gives . The leaf term has that same order, completing the proof. Notice how the leaf cost participates in the final result rather than disappearing from the analysis.
Proof X-ray
Depth does not count all calls
The logarithmic height says how many times one input can be halved on a single root-to-leaf chain. Multiplying the work at one node by that height is valid only if it accounts for every other node too. The level factor supplies the missing multiplicity. In a balanced recurrence, the geometric ratio tells us whether work is concentrated near the root, spread evenly by level, or concentrated near the leaves.
Pascal's identity offers a second subset count: for . Fix one element. Subsets omitting it are counted by the first term; subsets containing it correspond, after deletion, to -element subsets of the remaining set. The cases are disjoint and exhaustive. The boundary counts then support a dynamic-programming table. Direct recursion, without a table, repeatedly evaluates the same pairs of parameters; a correct recurrence and an efficient implementation are separate achievements.
Worked examples
Worked example 1.3.8
(Three roles or one committee)
Assigning three distinct students from eight to chair, secretary and treasurer gives possibilities. Forming a three-person committee gives , because every committee has six orderings. If one student may occupy several positions, the role assignments instead number . None of these answers is intrinsically more correct: they count different specified objects.
Worked example 1.3.9
(What a forced collision actually guarantees)
Eleven distinct keys are mapped into four buckets. The pigeonhole bound guarantees a bucket with at least keys. Loads show that a larger universal bound is impossible. The theorem does not identify the bucket or a pair of colliding keys in advance. It also does not imply that every bucket has at least two keys: loads satisfy the assignment rules too.
Worked example 1.3.10
(A deeper branching factor changes the cost)
For and on powers of two, level costs , and there are leaves. Summing gives . At , the intermediate costs are , and . The tree height is three, but its total work is not . Here , and the theorem correctly gives .
For comparison, one half-size recursive call with constant work has and therefore logarithmic cost. Two half-size calls with linear combination work have and therefore cost , as in merge sort. Four half-size calls with linear combination work give the quadratic example above. These comparisons become meaningful only after establishing that the actual algorithm makes the stated calls and incurs the stated local cost.
Not every recurrence is balanced. For fixed constants and , let and . Expansion gives . Applying a half-size theorem to this recurrence would silently change the algorithm. This linear-depth pattern describes, for example, a recursive partitioning procedure that repeatedly leaves a single remaining subproblem of size one less than before, with linear work per call. A balanced average-case intuition cannot replace a worst-case recurrence.
From loop executions to growth bounds
A cost bound begins with a particular operation and a precisely stated input size. Consider a procedure that examines every pair of positions in an array of length , using zero-based indices. For each , it visits and compares the two entries. When , the inner range is empty. Let count only these entry comparisons; for there are none.
For a fixed there are choices of . Adding over the outer loop gives
To prove the last equality, write the sum once in ascending and once in descending order. Each of the paired terms totals , so twice the sum is . This also holds for and , when the comparison count is zero. The formula counts unordered pairs of distinct positions exactly once: their smaller index is and their larger one is . Equal values at two positions do not make the positions identical.
For every integer , , hence
These fixed constants prove , not just an upper bound. If loop-control instructions take constant time per visit and there is constant initialization, their additional work leaves the total running time for large . This conclusion assumes constant-time entry access and comparison; for long strings, for example, one comparison can itself depend on string length.
Proof X-ray
A nested loop needs a sum, not a guess
Two loops do not automatically mean executions of the inner body. Here the inner-loop lengths are , not all . The exact sum supplies both the upper and lower bounds. If the inner loop had only one iteration for each outer index, the count would instead be linear.
Worked example 1.3.11
(What changes when a search stops early?)
Sequential search compares a target with array entries from left to right and stops at the first match, or after the last entry if none matches. On a length- input, its entry-comparison count is if the first match is at one-based position , and if the target is absent. For , the best count over all arrays and targets is one, achieved by a first-position match; the worst is , achieved by absence. Thus the best-case comparison count is and the worst-case count is . For an empty array both are zero.
A bound on the worst-case function automatically bounds every individual input of that size, but a bound for one favorable input does not bound all others. An average-case statement needs a specified probability distribution on inputs; neither the best nor the worst case determines that distribution.
Quick check
(A second procedure visits positions and, for each , visits once. How many visits occur, and what is the growth rate?)
Solution · Answer
The inner body runs times, so the total is ; the value is zero when . For it lies between and , hence is . The two loops enumerate different pairs: swapping the coordinates of every strict off-diagonal pair in the first gives exactly the strict off-diagonal pairs in the second. The second also includes one diagonal pair for each , so its count exceeds the first by .
Common mistakes
Common mistake
(Domain and codomain belong to the function)
A domain and codomain are part of a function's specification. The assignment from the real numbers to the real numbers is not surjective, but the same assignment to the nonnegative reals is surjective. It remains noninjective because one and minus one have equal images. These statements are consistent because injectivity and surjectivity ask different questions.
Common mistake
(Reading “choose three” as order-free)
Do not treat the phrase “choose three” as evidence that order is irrelevant. The surrounding task determines whether selected objects receive distinct roles. Likewise, repetitions may be forbidden by injectivity or allowed by the input model; a formula is useful only after those choices have been stated.
Counterexample mode
Not all symmetries produce the same number of descriptions
The ordered lists , and describe one multiset, giving three orderings, while has six. Dividing all length-three lists by therefore does not count multisets correctly. The subset formula works because its distinct-element hypothesis makes every fiber have the same size.
Common mistake
(An upper bound is not an exact growth rate)
An upper bound does not say that the cost is exactly quadratic or even that quadratic growth is necessary. A linear function is also . Use a matching lower bound for a conclusion, and state whether the analysis concerns worst-case, average-case or some restricted family of inputs.
Summary
Counting begins with the object: an arbitrary function, an injection and a subset have different multiplicities. A uniform fiber size justifies dividing an ordered count; pigeonholes bound the largest fiber when an assignment is crowded. Recurrence analysis similarly counts all call occurrences and sums their work. Explicit base cases, branching factors and cost models prevent a correct-looking formula from describing the wrong problem.
Exercises
Quick check
(How many functions map a four-element set to a three-element set? How many are injective? Explain the two answers without a negative factorial.)
Solution · Answer
Every one of the four inputs has three independent assignment choices, so there are functions. There are no injections: four distinct inputs cannot occupy three output values without a collision. The injection formula with is not applicable with ; the pigeonhole argument handles this case directly.
Quick check
(Prove that the number of simple undirected graphs on a fixed labeled set of vertices is .)
Solution · Answer
A simple undirected edge is an unordered pair of distinct vertices, and there are such pairs. Each pair is either present or absent, independently of the choices for other pairs. This is a bijection between labeled simple graphs and subsets of the possible edge set, giving the stated power of two. Loops and directed edges are excluded by the hypotheses.
Quick check
(Evaluate and interpret Pascal's identity for this particular count.)
Solution · Answer
The count is . Fix one of the ten elements. The four-element subsets omitting it number , and those containing it number . Their disjoint union gives .
Quick check
(Is in ? Is it in ? Justify the two conclusions from eventual inequalities.)
Solution · Answer
For positive integers , , giving , hence the first upper bound. For the second, is unbounded: for any proposed constant , an integer violates . Thus no eventual linear upper bound exists.
Exercise 1.3.12
(Analyze , on powers of two. Give an exact expression as well as an asymptotic bound.)
Core
Solution(3)
- 1
Sum the work by level
At level there are nodes of size , so the level costs .
- 2
Add the levels and the leaves
With and leaves of cost one, , which agrees with .
- 3
Read off the growth rate
Hence ; the root-level quadratic work already supplies the lower bound.