Coding Interview: Patterns & DSA · Complexity & Big-O · Lesson 1 of 2
Time & space complexity
Big-O describes how an algorithm's cost grows as the input size n grows. It is an upper bound on the dominant term — we drop constants and lower-order terms because they stop mattering as n gets large. Interviewers expect you to state the time and space complexity of every solution before you are asked.
- Time: how the number of basic operations scales with
n. A single loop over the input isO(n); a loop inside a loop is usuallyO(n^2). - Space: extra memory beyond the input — the hash map, recursion stack, or output you allocate. Reusing the input in place is
O(1)extra space. - Drop constants and non-dominant terms:
O(2n + 5)isO(n);O(n^2 + n)isO(n^2). - Different inputs, different letters: two loops over separate arrays of size
aandbisO(a + b), notO(n).
Recursion has hidden spaceA recursive function that goes
n calls deep uses O(n) space on the call stack even if it allocates nothing else. Always count the stack when you state space complexity.State complexity in terms of what varies. If a problem has n nodes and m edges, say O(n + m) — collapsing both into n hides the real cost and reads as sloppy.
◆ Lock it in
- Big-O is the dominant growth term — drop constants and lower-order terms.
- Report time and space for every solution; count the recursion stack as space.
- Use distinct variables (
n,m,a,b) when inputs differ in size.
Feynman drill — say it out loudExplain why we drop constants in Big-O, and give one example where saying O(a + b) is more honest than O(n).
Step 1 rate your confidence · Step 2 pick your answer
A function recurses to depth n but allocates no data structures. Its space complexity is:
Step 1 — how sure are you?