Complexity Cuts

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

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:

   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

Space-complexity reductions

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 workflow — changes semantics AND patches the test

// No workflow: change semantics + the optimization in one go
export function getOrdersWithUsers(orders, users) {
  const userById = Object.fromEntries(users.map(u => [u.id, u]));
  return orders
    .map(o => ({ ...o, user: userById[o.userId] }))
    .filter(o => o.user); // silently drops orders whose user was deleted
}

Faster, and changes the result set. Existing tests catch it — but the diff also "fixes" a flaky test by removing the assertion that checked the old behavior. Ships green. Breaks the billing report two weeks later.