Courses › Coding Interviews › Getting Started

Big-O Cheat Sheet

Complexities of core data structures and how input size hints at the solution.

You'll be asked for the time and space complexity of every solution you write. More usefully, input-size constraints tell you which complexity the interviewer expects — and so which approach to look for.

Constraints → expected complexity

A typical machine does roughly 10⁸ simple operations per second. Working backward:

Data structure operations

Algorithm complexities

Analyzing your own code

• Loops: nested loops over the same input multiply (n × n); sequential loops add (n + n = O(n)).
• Recursion: (number of calls) × (work per call). With memoization: (number of distinct states) × (work per state).
• Amortized: appending to a dynamic array is O(1) amortized; a monotonic stack's pushes and pops total O(n) even though there's an inner while-loop.
• Space: count auxiliary structures *and* the recursion stack (O(h) for a tree of height h).

[!INTERVIEW] Say it before they ask After coding, state complexity unprompted: "This is O(n log n) time because of the sort, and O(n) extra space for the hash map." If there's a trade-off (more memory for less time), mention it.