sickn33/agentic-awesome-skills/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.

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

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

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

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

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

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.

With the workflow — one transformation, semantics preserved

// Workflow applied:
//   Bottleneck: orders.map → users.find  (line 14)
//   Current: time = O(n·m), space = O(1)
//   Target:  time = O(n+m), space = O(m)
//   Transformation: precompute index Map<userId, User> outside the loop
//   Semantic risk: first duplicate and missing-user behavior preserved; Map equality matches strict equality for the declared finite integer user IDs. Validate that contract first.
//   Reverts so far: 0
export function getOrdersWithUsers(orders, users) {
  const userById = new Map();
  // Array.find returns the first duplicate, so keep the first value.
  for (const user of users) {
    if (!userById.has(user.id)) userById.set(user.id, user);
  }
  return orders.map(o => ({ ...o, user: userById.get(o.userId) }));
}

The example assumes finite integer IDs and side-effect-free ordinary objects; add duplicate-ID and missing-ID characterization cases before transforming. NaN IDs or getters require a different equivalence argument. One transformation. Existing tests stay untouched. Run them. If green, ship. If red, revert (don't patch). After 3 reverts, stop and load invariant-guard — the bottleneck is wrong, or the function has a contract no one wrote down.

Output discipline

When proposing or applying an optimization, your message must contain — in this order:

1. Bottleneck — file:line and one-sentence reason.
2. Current complexity — time = O(?), space = O(?).
3. Transformation — name from the playbook (or describe it if novel).
4. New complexity — time = O(?), space = O(?).
5. Semantic risk — anything callers might notice (ordering, stability, error timing). "None" is a valid answer if true.
6. Measured speedup — before → after with the ratio as N× faster (or asymptotic only if not measured). One line, honest numbers.
7. The diff.

If any of 1–6 is missing, the optimization is not ready to apply.

Stop conditions — do not optimize further when

• Asymptotic Big-O already matches a known lower bound for the problem.
• The input is provably small and bounded (n < ~100 and not on a hot path).
• The optimization would obscure correctness or harm readability without a measured win.
• The bottleneck is I/O or external service latency, not CPU/memory — go fix that instead.

Premature optimization past these points adds risk without payoff.

Rationalizations to watch for