# 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.

```ts
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.

```ts
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.