complexity-cuts

What this skill does

# complexity-cuts — Lower Big-O on Existing Code

`lemmaly` prevents bad complexity before code is written. **complexity-cuts** fixes it after the fact: code already exists, it works, but its time or space complexity is worse than necessary.

**Violating the letter of these rules is violating the spirit of the skill.** Adapting "just a little" is how a faster-but-wrong rewrite ships.

## When to Use This Skill

Use **complexity-cuts** when refactoring existing code that has poor Big-O:

- Nested loops, `O(n²)` or worse scans, repeated work, redundant allocations, blown memory.
- Stated symptoms: "this is slow on large inputs", "times out", "OOM", "too much memory", "reduce complexity", "optimize this algorithm".
- N+1 query patterns in ORMs (Prisma, Drizzle, SQLAlchemy, Django, ActiveRecord).
- `await` inside `for` over independent items causing serial latency.

For *preventing* bad complexity before code is written, use **`lemmaly`**. For math-level optimizations (Bloom, HLL, FFT, JL projection), escalate to **`mathguard`**.

## The Iron Law

```text
NO TRANSFORMATION WITHOUT EXISTING TESTS GREEN BEFORE AND AFTER
```

If the code has no tests, you write a characterization test first (golden input → current output). Then transform. Then verify the test still passes. If you skip this, the optimization can silently break callers — and faster-but-wrong is worse than slow-and-right.

## Non-negotiable rules

1. **State current and target Big-O before touching code.** In one line:
   - Current: `time = O(?)`, `space = O(?)`
   - Target: `time = O(?)`, `space = O(?)`
   - Dominant input dimension (n = what, how large in practice)

   If you cannot state current Big-O, you do not yet understand the code. Read more.

2. **Identify the bottleneck, do not guess.** Point to the exact line(s) responsible for the dominant term. Nested loop? Repeated linear scan? Recomputation? Allocation inside a hot loop? The fix lives there, not elsewhere.

3. **One transformation at a time, with a verify-revert-stop loop.** The loop is:

   1. Apply exactly one transformation from the playbook.
   2. Run the existing test suite (or the characterization test you wrote per the Iron Law).
   3. If any test breaks: **revert immediately.** Do not patch the test. Do not patch around the failure. Revert.
   4. Count reverts on this piece of code. If **3 reverts in a row**, STOP optimizing. The bottleneck is wrong, the transformation is wrong, or the code has invariants you have not modeled. Escalate to `invariant-guard` and write the missing contract — do not try a fourth transformation.
   5. Only after a transformation lands green: pick the next one.

   Stacked changes hide regressions. Patched tests hide regressions louder.

4. **Preserve semantics exactly.** Lower complexity must not change outputs, ordering guarantees, stability, or error behavior. If the optimization requires a semantic change (e.g. unordered output), call it out explicitly and confirm it is acceptable.

5. **No invented numbers.** Never write "10x faster" or "saves 200MB" without measuring. Write `<measured: TBD>` and move on, or actually measure with a representative input.

6. **Always report the measured speedup ratio after a transformation lands.** Once the new code is green, run a representative benchmark (same input, same machine, warm cache) and report `before → after` plus the ratio as `N× faster` (or `N× less memory`). One line, attached to the diff:

   ```text
   p50:  186 ms → 1.1 ms   (169× faster, n=20,000, 200 samples)
   ```

   If you cannot measure (e.g. the win is purely asymptotic on inputs you don't have), say so explicitly: `asymptotic only, no measurement — O(n²) → O(n)`. Never silently skip this step.

## The transformation playbook

The vast majority of real-world Big-O wins come from a small set of moves. Try them in this order:

### Time-complexity reductions

| Smell | Fix | Typical win |
|---|---|---|
| `for x in A: if x in B` where B is list/array | Convert B to `Set`/`Map` once | O(n·m) → O(n+m) |
| Nested loop computing pairs/joins | Hash-join on the key; index by lookup field | O(n·m) → O(n+m) |
| Repeated `.find` / `.indexOf` / `.includes` inside a loop | Precompute index `Map<key, item>` outside loop | O(n^2) → O(n) |
| Repeated recomputation of same value | Memoize / cache by input key | O(n·f(n)) → O(n + f(n)) |
| Sort inside a loop | Sort once outside | O(n^2 log n) → O(n log n) |
| Linear scan for min/max/median repeatedly | Heap / sorted structure | O(n·k) → O(n log k) |
| Recursive recomputation (naive Fibonacci shape) | Memoize, or convert to iterative DP | exponential → O(n) |
| String concatenation in a loop (some langs) | Use builder / `join` / `array.push` then join | O(n^2) → O(n) |
| Repeated regex compile in loop | Compile once outside | constant-factor, large |
| Counting / grouping via nested loop | Single pass with `Counter` / `Map<k, count>` | O(n^2) → O(n) |
| Sliding-window written as nested loop | Two-pointer / windowed sum | O(n^2) → O(n) |
| Repeated prefix sums | Precompute prefix array, O(1) range queries | O(n·q) → O(n+q) |
| Pairwise distance / containment checks on intervals | Sort + sweep line | O(n^2) → O(n log n) |
| Top-K via full sort | Heap of size K | O(n log n) → O(n log k) |
| Repeated set membership in loop body | `Set` once, reuse | O(n·m) → O(n) |
| `await` inside a `for` over independent items | `Promise.all` / batched concurrency | wall-clock O(n·latency) → O(latency) |
| ORM query inside a loop (N+1) | `IN (...)` / `select_related` / bulk fetch | O(n) round-trips → O(1) |

### Space-complexity reductions

| Smell | Fix | Typical win |
|---|---|---|
| Materializing whole list/array just to iterate | Generator / iterator / stream | O(n) → O(1) |
| Building intermediate arrays via chained `.map().filter().map()` on huge data | Single-pass loop or lazy pipeline | k·O(n) → O(n) (often O(1) extra) |
| Caching every intermediate result of a recursion | Rolling window (keep last k states) | O(n) → O(k) |
| Storing parents/visited for graph traversal when only count needed | Bitset / counter only | O(n) → O(1) |
| Copying input to mutate | In-place mutation when caller allows | O(n) → O(1) |
| Reading entire file before processing | Stream line-by-line / chunked | O(file) → O(chunk) |
| Deep-clone for safety in a loop | Clone once, or use structural sharing / immutables | O(n·m) → O(n+m) |
| Holding references that prevent GC (closures, listeners, caches) | Bound the cache (LRU), remove listeners, scope closures tightly | unbounded → bounded |
| Loading full result set from DB | Cursor / pagination / streaming query | O(rows) → O(page) |
| `JSON.parse(JSON.stringify(x))` for cloning | `structuredClone` or targeted copy | O(n) work and allocation removed |

### When you cannot lower asymptotic Big-O

Sometimes O(n log n) really is the floor. Then move to constant-factor wins:

- Replace pointer-chasing structures with contiguous arrays (cache locality).
- Hoist invariants out of loops.
- Avoid allocation in the hot loop (reuse buffers).
- Prefer typed arrays / native containers over boxed objects for numeric work.
- Batch syscalls / I/O.

State explicitly: "Asymptotic floor is O(n log n); applying constant-factor optimizations only."

## Required workflow

For each piece of code you optimize:

1. **Measure or estimate current Big-O.** Write it down.
2. **Identify the bottleneck line(s).** Point at them.
3. **Pick one transformation from the playbook.** Name it.
4. **Apply it.** One change.
5. **Verify behavior.** Tests pass, or outputs match on a representative input.
6. **State new Big-O.** Time and space.
7. **Repeat if more wins exist and are worth the complexity cost.**

## Canonical example — workflow vs no-workflow

The same optimization with and without the verify-revert-stop loop.

**Bottleneck.** `getOrdersWithUsers()` runs 10s on 10k orders. Cause: `users.find(u => u.id === o.userId)` inside the map → O(n·m).

### Without the wor