complexity-derivationlisted

# Skill: complexity-derivation ## Premise Turn a piece of code (or a designed algorithm's structure) into a **cited** time + space complexity — never an intuited one. This is the shared engine the `algorithm-designer` agent, `/design-algorithm`, and `/analyze-complexity` all run on: every `O(...)` it emits names the exact construct it came from (the nested loop at `<path:line>`, the recurrence, the amortized argument), so the bound can be checked rather than trusted. It does NOT measure runtime — that is the profiler's job (`performance-optimizer`). It reasons about asymptotic growth from structure. ## When to run - Inside `/analyze-complexity` (derive each hot path's complexity) and `/design-algorithm` (derive the budget + each candidate's class). - Standalone when a `<path:line>` or a snippet needs a defensible big-O for a review or an ADR. - NOT for constant-factor questions ("is this 2× faster?") — that needs measurement, not derivation. ## Inputs (precise contract) | Input | Source | Required | |---|---|---| | The code or algorithm structure | `<path:line>` / snippet / pseudocode | YES | | The growth variable(s) | the caller (`n` = ?, `k` = ?, `V`/`E` for graphs) | YES — an `O(...)` with an undefined variable is meaningless | | Cost of called operations | the language's container/op guarantees (hash get `O(1)` avg, sort `O(n log n)`, list index-of `O(n)`) | YES — the derivation is only as right as its leaf costs | | Hotness / scale (optional) | caller / `--scale`