LiveCodingInterview.com
← Articles

Big O Cheat Sheet: How to Analyze Time Complexity in Coding Interviews

Nearly every coding interview ends with, "What's the time complexity?" You are not being asked to count CPU cycles. Interviewers want to know whether your approach scales, and whether you can spot bottlenecks before they become bugs in production.

Big O describes how runtime grows as input size grows, and it ignores constants and lower-order terms, which is why O(3n + 50) is still O(n). If you can state complexity confidently and tie it back to your code structure, you signal senior-level thinking even on medium problems.

What Does Big O Actually Mean?

We write O(f(n)) to say that for large enough input, runtime grows no faster than f(n). The variable n almost always means the primary input size, such as array length, string length, or number of nodes. When two inputs matter, like a grid with n rows and m columns, use both and write O(nm) instead of picking one.

Interview tip: always define n out loud before analyzing. Saying "let n be the number of users in the feed" removes ambiguity and buys you a few seconds to think.

How Do You Read Loops for Complexity?

Loops are the fastest way to estimate complexity. Count how many times the innermost work runs relative to n.

Single pass gives O(n): one loop over the input.

for (let i = 0; i < nums.length; i++) {
  // constant work
}

Nested loops give O(n²): every element paired with every other element.

for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    // constant work
  }
}

A triangle loop is still O(n²): the inner loop starts at i instead of 0, but you still iterate roughly n²/2 times.

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    // compare pairs
  }
}

Rule of thumb: k nested loops that each scale with n give O(n^k), so three nested loops over n is O(n³).

Why Don't Constants Change Big O?

These loops all look different but are all O(n):

for (let i = 0; i < 3 * n; i++) { /* ... */ }
for (let i = 0; i < n + 100; i++) { /* ... */ }
for (let i = 0; i < n; i += 2) { /* ... */ }

Interviewers care about growth rate, not whether you loop 2n or 5n times, so drop constants when you speak and say O(n), never O(2n).

What Happens When Code Runs in Multiple Passes?

When code runs in sequential phases, the slowest phase dominates the total.

function process(nums) {
  nums.forEach(() => { /* O(n) */ });

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      /* O(n²) */
    }
  }

  nums.sort(); // O(n log n)
}

Total: O(n) + O(n²) + O(n log n) reduces to O(n²), since the quadratic nested loop is the bottleneck. Mention that explicitly; it shows you know which line actually matters.

How Do You Handle Two Different Input Sizes?

Grids, graphs, and string matching often depend on two dimensions:

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    // visit cell (i, j)
  }
}

Complexity is O(nm), not O(n²), unless m and n happen to be equal. For a square grid, say O(n²), but for comparing two strings of length n and m, many DP solutions are genuinely O(nm) and should be named that way.

How Do You Analyze Recursive Time Complexity?

Recursive runtime equals the number of calls multiplied by the work per call, excluding deeper recursion.

Linear recursion gives O(n): one recursive call per level.

function countdown(n) {
  if (n === 0) return;
  countdown(n - 1);
}

n calls at O(1) each gives O(n) overall.

Binary recursion gives O(2^n): two calls branch at each level, as in naive Fibonacci.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

The call tree doubles at each level, so total calls grow exponentially, roughly O(2^n). In interviews, name this immediately and offer memoization or bottom-up DP to bring it down to O(n).

Divide and conquer is often O(n log n): merge sort splits in half, giving log n levels, and does O(n) merge work per level, for O(n log n) overall. The same pattern shows up in fast FFT-style problems and some tree algorithms.

What Does Space Complexity Mean?

Space complexity measures extra memory your algorithm needs beyond the input itself, and interviewers expect you to state it in the same breath as time complexity, not as an afterthought. Auxiliary space is the memory you allocate on top of the input, such as a hash map, a result array, or a recursion stack, and it is what "O(1) space" or "O(n) space" almost always refers to in an interview answer. Total space, by contrast, includes the input itself, so a function that just reads through an existing array without copying it uses O(1) auxiliary space even though the input is O(n).

An algorithm is in-place when its auxiliary space is O(1), meaning it rearranges the input using only a constant number of extra variables. Swapping two array elements to reverse a list in place is O(1) space; copying the list into a new array first and returning that is O(n) space, even though both approaches solve the same problem. Recursion has a hidden space cost too: each call frame sits on the call stack until it returns, so a recursive function with n nested calls uses O(n) space on the stack even if it never allocates a single array, which is exactly why the recursive binary search on the binary search guide is O(log n) space while the iterative version is O(1).

What Is Amortized Time Complexity?

Some operations are usually cheap but occasionally expensive, and amortized analysis averages that cost over a long sequence of operations rather than reporting the worst single call. The textbook example is appending to a dynamic array, like a JavaScript array or Python list: most appends are O(1) because there is spare capacity, but every so often the array is full and must be reallocated and copied into a larger block, which is O(n) for that one call. Spread across n appends, the total copying work is O(n), so the amortized cost per append is still O(1), even though any individual append could be the expensive one.

Hash map insertion works the same way. A single insert can trigger a resize of the underlying table, but because resizes get exponentially rarer as the table grows, the amortized cost per insert stays O(1). Naming "amortized O(1)", instead of just "O(1)", for a dynamic array append or a hash map insert is a small detail that signals you understand why the worst case and the typical case can differ.

What Is the Big O Cheat Sheet for Interviews?

Memorize the ordering, and when comparing approaches, refer to where each one sits on this ladder, best to worst:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

O(1), constant, excellent: a hash map lookup, an array index access, pushing to a stack. None of these grow with input size.

O(log n), logarithmic, excellent: binary search, balanced BST operations, repeatedly halving the search space. If you eliminate half the remaining data at each step, think log n.

O(n), linear, good: a single scan, two pointers on a sorted array, BFS or DFS when each node is visited once. Often the best you can do if you must examine every element at least once.

O(n log n), linearithmic, good: efficient sorting, merge sort, heap operations over n items, divide-and-conquer with a linear combine step. If your solution sorts the full input, start your analysis here.

O(n²), quadratic, fair: nested loops, brute-force pair checking, simple DP on small grids. Common in naive solutions, and interviewers often ask how you would improve on it. O(n³) and higher polynomial classes sit here too, just further down the ladder, acceptable for small, bounded n, but worth flagging as a target to optimize.

O(2^n) and O(n!), exponential and factorial, bad: generating all subsets or all permutations. Fine for n up to about 20 in backtracking problems, but unusable at any real scale. Name the pattern the moment you see a bitmask or a "try every ordering" approach.

Ranking a solution on this scale out loud, not just naming its Big O, is what tells an interviewer you know whether the complexity you landed on is actually acceptable for the problem's constraints, not just correctly computed.

What Do Interviewers Want to Hear?

State Big O for time and space right after you describe the approach, not after you finish coding, and tie the complexity to a specific line: "the nested loop over pairs gives O(n²)" is far stronger than a bare number with no justification. Compare your approach to the alternatives you are not choosing, such as "sorting first is O(n log n), while a hash map lookup is O(n) average," and call out the trade-offs you are making on purpose, like accepting O(n) extra space in exchange for O(n) time instead of O(n²).

You do not need a formal proof for any of this. You need a consistent method: find the hot loop, count how many times it runs, express that count in terms of n, drop the constants, and keep the dominant term.

When Is Your Solution Too Slow for the Constraints?

Typical online judges and interview platforms handle roughly the following without timing out: O(n) or O(n log n) is safe for n up to 10^6 or more, O(n²) is fine for n around 10^3 to 10^4, and O(2^n) only works when n stays at 20 to 25 or below. If your brute force is O(n²) and the stated constraint is n = 10^5, stop and rethink before you start coding, because that constraint is a direct hint about the complexity the interviewer expects.

Frequently Asked Questions

Do I need to know the exact constant factors, or just the growth rate?

Just the growth rate in almost every case. Interviewers care whether your algorithm is O(n) or O(n²), not whether it is 2n or 5n operations, since growth rate is what determines behavior at scale and constants rarely change which algorithm is the right choice.

What is the difference between O, Omega, and Theta?

Big O gives an upper bound (no slower than this), Omega gives a lower bound (no faster than this), and Theta means both bounds match (exactly this rate). In interviews, "Big O" is used loosely to mean the tight bound, Theta, even though that is technically imprecise, and interviewers rarely push back on the distinction.

Should I state best case, worst case, or average case?

State worst case by default, since that is what Big O means unless you say otherwise, and call out best or average case explicitly when it changes your answer meaningfully, like quicksort's O(n²) worst case against its O(n log n) average case.

Why do two algorithms with the same Big O run at different speeds in practice?

Because Big O hides constant factors and lower-order terms that still matter on real hardware: cache locality, memory allocation, and branch prediction all affect wall-clock time without changing the asymptotic class. Both facts are true at once. Two O(n log n) sorts can have very different real-world speed, and Big O is still the right first-order comparison for an interview answer.

Is O(1) space ever actually zero memory?

No, O(1) space means constant memory that does not grow with input size, not zero memory. A handful of loop variables and pointers still take real memory; the point is that the count stays fixed regardless of whether n is 10 or 10 million.

How Should You Practice Applying This?

Work through the study guide on LRU Cache, where every operation is O(1) and you should be able to explain why out loud. Then compare it with Merge Intervals from a Data Stream, where a heap gives O(log n) per insertion instead. Once both examples feel automatic, LeetCode patterns worth recognizing on sight shows how naming a pattern early and stating its complexity in the same breath is the habit that separates a confident answer from a guessed one.