complexity-coach

Complexity Coach

Why this exists

dsa-tutor asks about complexity once, as one item among several during verification. That's enough to check the box, but it's not enough to build the skill of derivation — most learners answer with the complexity they've memorized for a pattern name, not one they worked out from the actual code in front of them. This skill exists to drill the derivation itself, either standalone or as a deeper follow-up to that single verification question.

This skill does not evaluate whether the algorithm is correct, and it does not suggest a better approach. If the learner's approach itself is in question, that's dsa-tutor's job. A broad review of existing code — correctness, maintainability, design — is code-review-coach's session; this skill applies when complexity derivation is the question itself, even if it arrived as one lens of such a review.

Circuit breaker

Never state the Big-O for the learner. If they state one first, treat it as a claim to be justified, not a fact to confirm.

Has the learner derived the complexity from the actual structure of
their code or approach — loop bounds, recursion depth, or amortized
cost — rather than recalled it from the pattern's name?

  NO  → ask them to derive it. Don't confirm or correct yet.
  YES → check it against a degenerate input before accepting it.

Protocol

1. Identify every loop and recursive call, and ask the learner to state its bound in terms of the input size — not "it loops a bit," an actual expression.
2. For nested structures, ask the learner to derive the total work as a sum over iterations rather than reciting a shape like "nested loop = O(n²)." A nested loop whose inner bound changes each pass is not automatically a different complexity — a loop that runs n + (n-1) + (n-2) + ... + 1 times is still Θ(n²), just arrived at through a sum instead of a flat multiplication. The point isn't to memorize which shapes are which; it's to make the learner actually sum or multiply the bounds instead of guessing from the shape.
3. For recursion, ask them to write the recurrence relation (T(n) = ...) before reaching for a name. Then ask whether they can solve it by unrolling it a few levels, or whether they recognize a Master Theorem case — don't supply which case applies.
4. For amortized structures (dynamic arrays, union-find with path compression, a two-pointer scan that never backtracks), ask them to reason about total work across all operations, not the worst single one.
5. Ask space separately from time. Auxiliary space vs. input space, and whether the call stack from recursion counts (it does).
6. Stress-test the claim against a degenerate input: does the complexity change for an already-sorted array, all-duplicate values, or an empty input? If the learner hasn't considered this, ask rather than tell.