Big-O Notation Cheat Sheet: Time & Space Complexity

Big-O describes how runtime grows with input size n. Interviewers rarely care about exact constants — they care that you can name the complexity class and justify it. These are the tiers to memorize:

• O(1) — constant: array lookup by index, hash map lookup
• O(log n) — logarithmic: binary search, balanced tree operations
• O(n) — linear: single pass over an array, linear scan
• O(n log n) — linearithmic: efficient sorts, divide-and-conquer merges
• O(n²) — quadratic: nested loops over the input
• O(2ⁿ) — exponential: recursion over subsets, naive Fibonacci
• O(n!) — factorial: permutations

A fast way to estimate complexity: count the nested loops that depend on the input size. A single loop is O(n), two nested loops are O(n²). The moment you halve the search space each step, you are in O(log n) territory. Recursive calls that solve the full problem twice are the classic source of accidental O(2ⁿ).

// O(n): one pass
for (let i = 0; i < n; i++) total += arr[i];

// O(n²): nested dependent loops
for (let i = 0; i < n; i++)
  for (let j = i + 1; j < n; j++) pairs.push([i, j]);

// O(log n): halving the space each step
while (lo <= hi) {
  const mid = (lo + hi) >> 1;
  if (target === arr[mid]) return mid;
  target < arr[mid] ? (hi = mid - 1) : (lo = mid + 1);
}

Space complexity is the extra memory your algorithm allocates, not the input itself. In-place algorithms use O(1) extra space. Watch out for these common traps:

• A recursive solution with depth n uses O(n) call stack space even if no arrays are allocated.
• Building an output array of size n is O(n) space — acceptable, but say so.
• Hash maps buy speed with space; the trade-off should always be mentioned.

Before you write a single line, say: "A brute force would be O(n²), but a hash map lets me drop lookup to O(1), giving O(n) time and O(n) space." Naming the trade-off out loud is often what separates a hire from a pass. Memorize this cheat sheet and you will never freeze on the complexity question again.