TAOCP 5 Exercise 15

We are given a list of \(N\) records, each consisting of a person's name and the U.

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 15. [18] You are given a list of the names of a fairly large number of people born in the U.S.A., together with the name of the state where they were born. How do you count the number of people born in each state? (Assume that nobody appears in the list more than once.)

Verified: yes
Solve time: 7m26s

Solution

We are given a list of (N) records, each consisting of a person's name and the U.S. state where they were born. There are exactly 50 possible states. The task is to compute, for each state, the number of people in the list born there. (The assumption that no person appears more than once simply guarantees that each record corresponds to a distinct individual; it does not affect the counting method.)

Because the number of distinct keys (states) is a small constant (50), we can solve the problem in linear time without sorting. The optimal method uses direct addressing with an array of 50 counters.

Algorithm.

  1. Initialize an array (C[1..50]) to all zeros.
  2. For each record in the list:
    • Let (s) be the state name in the record.
    • Determine the index (i \in {1,\dots,50}) corresponding to (s) (e.g., via a fixed mapping from state names to indices, such as a perfect hash table or a small lookup array).
    • (C[i] \gets C[i] + 1).
  3. Output (C[1], C[2], \dots, C[50]) as the counts for the 50 states.

Correctness. We prove by induction on (k) ((0 \le k \le N)) that after processing the first (k) records, (C[i]) equals the number of people among those (k) records born in state (i).

  • Base case (k = 0): all counters are zero, which matches the empty list.
  • Inductive step: assume the invariant holds after (k-1) records. The (k)-th record has state (s) with index (i). The algorithm increments (C[i]), so (C[i]) becomes the previous count plus one, exactly the count among the first (k) records. All other counters are unchanged, so the invariant holds for (k).
    After all (N) records are processed, the invariant gives the desired counts.

Termination. The loop processes each of the (N) records exactly once. Since (N) is finite, the algorithm terminates.

Complexity. Each record is examined once. Mapping a state name to its index takes (O(1)) time because the number of states is constant (a perfect hash or a linear scan over 50 names is bounded by a constant). Hence the total running time is (O(N)). The extra space used is the array of 50 counters, i.e., (O(1)) space.

This method is asymptotically optimal: any algorithm must read all (N) records, giving an (\Omega(N)) lower bound on the running time.

\boxed{\text{Use an array of 50 counters, one per state. Scan the list once, incrementing the counter for each person's state. The final counters are the required counts.}}

Notes

If the list were stored on external media (e.g., magnetic tape) and too large to fit in main memory, one could first sort the records by state using an external merge sort, then make a single pass over the sorted data to count consecutive records with the same state. However, the problem statement does not impose external‑storage constraints, so the direct counting method above is both simpler and faster.