cheat sheets / theory
Big-O & CS Theory Cheat Sheets for Interviews
The complexity reference every candidate revises from, the classic theory card, and regex decoded. Plus the part that actually gets people through interviews: what Big-O deliberately hides.
When you are preparing for a coding interview or an algorithms exam, a textbook is the wrong shape of tool. You need the key facts in one place and a clear sense of which ones matter. These three references are the classics people actually revise from, and the sections after them cover the reasoning that turns memorized complexities into answers you can defend under questioning.
01 · THE REFERENCES
Complexity, theory & regex
The high-yield references worth having open. The theoretical CS card is a genuine artefact of its era, dense enough that it rewards repeated visits rather than one read.
- Big-O Cheat Sheet ↗Time and space complexity for every common data structure and sorting algorithm, colour-coded. The canonical interview-prep reference.bigocheatsheet.com
- Theoretical CS Cheat Sheet (PDF) ↗Steve Seiden's dense classic — series, combinatorics, recurrences, and identities packed onto a few pages. A legend for good reason.tug.org
- Regex Cheat Sheet ↗Anchors, character classes, quantifiers, and lookarounds — the theory of regular expressions, made practical.quickref.me
02 · WHAT BIG-O MEANS
Growth rate, not speed
Big-O describes how the work grows as the input grows. It deliberately discards constant factors and lower-order terms, because those depend on hardware and implementation details that change. This is what makes it portable, and it is also the source of most confusion about it.
The practical consequence: an algorithm with better asymptotic complexity is not automatically faster on your data. Constants matter enormously at small sizes, and "small" in modern terms can mean thousands of elements. A linear scan over a contiguous array often beats a theoretically superior structure because it uses the cache well, and a simple quadratic sort is genuinely the right choice for tiny inputs. Big-O tells you which algorithm wins eventually. It does not tell you where the crossover is.
Average, worst, and amortized are different claims
These get conflated constantly, and interviewers notice. Hash table lookup is constant time on average but linear in the worst case when everything collides. Appending to a dynamic array is amortized constant time: most appends are cheap, an occasional one triggers a resize, and the average over a sequence stays constant. Quicksort is usually the fastest comparison sort in practice and quadratic in its worst case. Being precise about which case you are describing is a large part of sounding like someone who understands the material rather than someone who memorized a table.
03 · USING IT IN INTERVIEWS
What the complexity question is really testing
When an interviewer asks for the complexity of your solution, they are rarely checking whether you memorized a chart. They want to see whether you can look at your own code and reason about it: which loop dominates, what the recursion does to the input size, and what the data structure you chose actually costs.
Space complexity is the half people forget. Recursion consumes stack proportional to its depth, and a solution that builds an intermediate copy of the input has a real memory cost even if its running time looks good. Volunteering the space analysis alongside the time analysis is a cheap way to demonstrate thoroughness.
04 · THE REST OF THE THEORY
Recurrences, combinatorics, and regular languages
The theoretical CS card covers the mathematics that sits behind algorithm analysis: summations, recurrence relations, and combinatorial identities. This matters most for recursive algorithms, where the running time is naturally expressed as a recurrence and you need a way to turn that into a closed form. Recognizing the standard shapes, particularly divide-and-conquer recurrences, saves a great deal of work.
Regular expressions belong on a theory page for a reason that is easy to miss: they are a formal language class with defined limits. Regular languages cannot count arbitrarily deep nesting, which is precisely why matching balanced brackets or parsing HTML with a regular expression fails. Knowing that boundary is more useful than memorizing syntax, because it tells you when to stop reaching for a pattern and reach for a parser instead.
05 · FAQ
Frequently asked questions
Are these CS theory cheat sheets free?
Yes. All three are free to access with no account. The Big-O reference and the regex sheet are free web pages, and Steve Seiden's theoretical CS card is a freely distributed PDF.
Does a better Big-O always mean a faster program?
No. Big-O describes how work grows with input size and deliberately ignores constant factors, so an algorithm with worse asymptotic complexity can be faster on realistic data. Simple approaches often win on small inputs because they use the cache well and have low overhead.
What is the difference between average, worst, and amortized complexity?
Average describes typical inputs, worst case describes the most unfavourable input, and amortized describes the average cost across a sequence of operations. Hash lookup is constant on average but linear in the worst case, while appending to a dynamic array is amortized constant because occasional resizes are spread across many cheap appends.
How much Big-O do I need for a coding interview?
Enough to analyse your own solution out loud, which usually means recognizing a few patterns rather than memorizing a table. Interviewers want to see you identify the dominant loop, reason about recursion depth, and state the space cost alongside the time cost.
Why can't regular expressions parse HTML?
Because regular languages cannot handle arbitrarily deep nesting, and HTML is a nested structure. That limitation is formal rather than a matter of writing a cleverer pattern, which is why a real parser is the right tool for structured formats.