L15: Algorithms II: Complexity and Tradeoffs

Puzzle Stations

1. **Operation count:** a list of 3 items has 3 possible pairs, 6 items have 15, and 12 items have 66. Explain why pair checking grows quadratically.
2. **Contract tests:** for a duplicate-checking helper, choose one input each for empty, one item, a repeated ID, and all unique IDs. Write the expected boolean for each.
3. **Binary-search precondition:** binaryHasId(["f", "a", "m", "c"], "c") can return false even though "c" is present. Trace why the unsorted input breaks the strategy.
4. **Lookup choice:** choose scan, binary search, or a Set for each case: one lookup in a short unsorted list; many lookups in an already sorted list with little spare memory; many membership checks with memory available.
5. **Subset warning:** if a feature must list every subset, each added item doubles the output. Name one way to reduce the problem instead of waiting for a faster implementation.

Programming Challenge: Same Contract, Different Strategy

Both helpers must return whether an ID appears more than once. Complete the Set version, then run every case against both helpers.

function hasDuplicateIdSlow(ids: readonly string[]): boolean {
  for (let left = 0; left < ids.length; left += 1) {
    for (let right = left + 1; right < ids.length; right += 1) {
      if (ids[left] === ids[right]) return true;
    }
  }
  return false;
}

function hasDuplicateIdFast(ids: readonly string[]): boolean {
  const seen = new Set<string>();

  for (const id of ids) {
    // TODO: return true when id is already in seen.
    // TODO: otherwise add id to seen.
  }

  // TODO: return false after every id has been checked.
}

const duplicateCases: { ids: readonly string[]; expected: boolean }[] = [
  { ids: [], expected: false },
  { ids: ["a"], expected: false },
  { ids: ["a", "b", "a"], expected: true },
  { ids: ["a", "b", "c"], expected: false },
  { ids: ["a", "a", "b"], expected: true },
];

for (const { ids, expected } of duplicateCases) {
  const slow = hasDuplicateIdSlow(ids);
  const fast = hasDuplicateIdFast(ids);
  if (slow !== expected || fast !== expected) {
    throw new Error("duplicate helpers failed a contract case");
  }
}

Explain the cost after the tests pass: the slow helper is quadratic in the worst case; the Set helper is linear expected time overall and uses extra memory.

Exercise 2: Count the Work

Complete countPairComparisons. It must count every possible pair, even if two IDs are equal, so that the count describes the full nested-loop cost.

function countPairComparisons(ids: readonly string[]): number {
  // TODO: write nested loops where right starts at left + 1.
  // TODO: add one for each pair and return the total.
}

const countCases: { ids: readonly string[]; expected: number }[] = [
  { ids: [], expected: 0 },
  { ids: ["a"], expected: 0 },
  { ids: ["a", "b", "c"], expected: 3 },
  { ids: ["a", "b", "c", "d", "e", "f"], expected: 15 },
  { ids: Array.from({ length: 12 }, (_, index) => String(index)), expected: 66 },
];

for (const { ids, expected } of countCases) {
  if (countPairComparisons(ids) !== expected) {
    throw new Error("pair count did not match the expected total");
  }
}

Afterward, say what n is and why doubling n makes the pair count grow by roughly four times.

Common Bugs

• Using binary search without a sorted-array promise.
• Calling a whole Set strategy constant time without counting the one-pass setup.
• Comparing a lucky early exit with a worst-case guarantee without naming the case.
• Choosing a faster data structure before asking whether the real input size needs it.

Bonus Puzzles

• Trace a binary search on a sorted array and name each discarded half.
• Make a duplicate appear first and then last; compare the observed early exit with the same worst-case label.
• Ask AI for a growth estimate, then verify it with a named input size and repeated operation.