• Computer science

CS theory: you cannot code your way past the proof

Strong programmers frequently struggle with computer science theory, and are surprised by it. Complexity analysis, automata, formal proofs and correctness arguments are not programming — they are mathematics, they resist the build-it-until-it-works approach that serves you so well in code, and no amount of implementation fluency substitutes for them.

5 min readSubjects

Theory is a maths subject wearing a hoodie

You cannot debug your way to a proof. You cannot run it and see. The feedback loop that makes programming learnable — write it, run it, fix it — simply doesn't exist here, and students who have only ever learned that way find themselves without a method.

So use the maths method: attempt before you look, reproduce proofs from a blank page, and explain each line's justification rather than nodding along to it.

Algorithms: implement, then abstract

  • Implement it from memory. If you can't, you don't know it, and you were about to convince yourself you did.
  • Then derive its complexity from scratch — don't recall the answer. The derivation is the examinable skill; the O(n log n) is trivia.
  • Know why it's correct, not just that it is. The invariant is the actual content.
  • Know when it fails, and what you'd use instead. This is the question that separates candidates.

Proof techniques are patterns, and there are few

Induction, contradiction, construction, reduction, pigeonhole. There are not many, and recognising which one a problem wants is the whole skill — which makes it an interleaving problem. Practise mixed proof problems, never one technique at a time, because a chapter titled 'Induction' has already told you the answer.

Common questions

Why is CS theory harder than programming for me?

Because it's mathematics, and the write-it-run-it-fix-it loop that makes programming learnable doesn't exist. You can't debug a proof.

How do I learn algorithm complexity?

Derive it from scratch rather than recalling it. The derivation is the examinable skill; knowing that mergesort is O(n log n) is trivia.

How do I get better at proofs?

Practise mixed proof problems so you have to choose the technique. A chapter labelled 'Induction' has already told you the answer, which means it trains nothing.

Try it on your own material

Upload your notes, slides or lecture recordings and get a tutor that answers only from them — and says so when they don't cover it.

$12/month, or $8/month billed yearly · cancel in two clicks