Algorithm Intuition: Worked Examples

Work through each trace before reading the explanation. Then solve the transfer task without the page open.

Example 1: Search depends on sorted input

Search for 2 in [1,4,2,8]. Binary search can discard the half containing 2 because its sorted-input precondition is false. A faster implementation cannot repair that contract.

On sorted [1,2,4,8], maintain a half-open candidate interval [lo,hi). Midpoint value 4 is too large, so set hi = mid; the next midpoint is 2. The invariant says that any existing target remains in the candidate interval, and each unsuccessful step shrinks it.

Example 2: Operation count is not elapsed time

Algorithm A performs n comparisons; B performs n squared. At n=10 the counts are 10 and 100; at n=1000 they are 1000 and 1,000,000.

This predicts different growth, not an exact timing ratio. Comparison cost and initialization can dominate small inputs. Record the input family, operation counts, and elapsed time separately. A model explains a growth curve; measurements expose implementation and environment costs.

Transfer and self-check

How many halvings reduce 1024 candidates to one? Check: 10 reductions, which need not equal the exact number of equality tests in a particular implementation.

Evidence to keep

Save your first attempt, corrected reasoning, and transfer result as checkpoint evidence. A matching final answer without an explanation is insufficient. Continue with the guided lab and use the reading guide to repair a specific gap.