Big O Interview Guide — explain complexity in one breath

The short version. Big O describes how an algorithm's runtime or memory grows as the input gets bigger. O(n) is linear — double the input, double the work. O(n²) is quadratic — double the input, quadruple the work. O(1) is constant — input size does not matter. In interviews, Big O is the language you use to defend that your code will hold up on a million rows, not just the three in the example.

Here is the pattern from a hundred mock screens: "looks good, but what is the complexity?" The issue is almost never that candidates do not know Big O. The issue is that they treat complexity analysis like cleanup work — the thing you say after the code is written, instead of the thing that shapes why you wrote it that way.

In StrongYes's own Google and Snap company guides, clean time and space reasoning is called out as part of the coding bar. AlgoCademy's interview guide puts it well: "explain first, label second — saying the complexity without explanation sounds memorized; walking through it sounds competent." That is the right way to think about it: Big O is part of the solution, not commentary after the solution.

“Complexity is not commentary after the solution. It is part of why you wrote the code that way.”

What Big O actually means in an interview

Big O describes how the work grows as the input grows.

It does not mean:

• exact runtime on your laptop
• exact milliseconds in production
• counting every constant operation forever
• pretending hardware and language details do not matter

In interviews, Big O is a communication shortcut. You are showing that you can:

1. name the relevant input size
2. find the dominant operation
3. ignore the noise without ignoring the bottleneck
4. separate runtime from extra memory

That is why good candidates sound calm. They are not guessing. They are walking through a repeatable process.

The 4-step script that works out loud

When the interviewer asks for complexity, use this order.

1. Define the input size

Say what n means before you do anything else.

Examples:

• "n is the number of elements in the array."
• "n is the number of nodes in the tree."
• "m and n are the grid dimensions."

If you skip this, the rest of the answer sounds fuzzier than it is.

2. Count the dominant operation

Ask: what repeats the most as the input grows?

• one pass through an array -> usually O(n)
• nested passes over the same array -> often O(n^2)
• sorting first -> usually O(n log n)
• tree or graph traversal -> often O(V + E) or O(n)

Do not count syntax. Count repeated work.

3. Simplify honestly

Drop constants and lower-order terms:

• O(2n) becomes O(n)
• O(n + n log n) becomes O(n log n)
• O(3n^2 + 5n + 7) becomes O(n^2)

But do not oversimplify different variables:

• O(m + n) does not become O(n)
• O(V + E) does not become O(n^2) unless the graph is dense and you say so

4. State extra space separately

This is where many otherwise good answers lose points.

Time complexity is not enough. You also need to say:

• whether you used a hash map or set
• whether recursion adds call-stack space
• whether a queue, stack, or result array grows with input size

Interviewers notice when someone says "O(1) space" after using a data structure that clearly grows with n.

The decision tree in your head

Here is the same 4-step script as a flowchart. When the interviewer asks for complexity, walk through this — it takes 10 seconds and catches the three mistakes most candidates make (wrong input size, missed sort cost, forgotten auxiliary space).

If the operation doesn't scale with input size at all — hash lookup, array index by position — it's O(1) and you're done. Otherwise, ask one question:

Diagram

Copy source

Rendering diagram...

The color encoding is the interview intuition: green complexities are usually fine to ship, amber is the realistic best you can do for many problems, and red means you should be actively looking for a better approach (or explicitly saying "the brute force is quadratic, here's how I'd improve it"). After the time answer lands, always add the space sentence from step 4 — the tree tells you the time class, not the space class.

Worked examples you can reuse

Example 1: nested-loop duplicate check

JS

Copy

function hasDuplicateBruteForce(nums) { for (let i = 0; i < nums.length; i += 1) { for (let j = i + 1; j < nums.length; j += 1) { if (nums[i] === nums[j]) return true; } } return false; }

How to say it:

• "n is the array length."
• "The outer loop runs up to n times, and for each position the inner loop may scan the remaining array."
• "That gives quadratic time, O(n^2)."
• "Extra space is O(1) because I only use loop variables."

That is already a complete answer.

Example 2: hash-set duplicate check

JS

Copy

function hasDuplicate(nums) { const seen = new Set(); for (const num of nums) { if (seen.has(num)) return true; seen.add(num); } return false; }

How to say it:

• "I scan the array once, so the loop is O(n)."
• "Set lookup and insert are average O(1), so total time is O(n)."
• "Space is O(n) in the worst case because the set can grow to hold every element."

That "average O(1)" detail is good interview hygiene — the formal term is amortized cost, and Interview Cake's Big O walkthrough explains the distinction cleanly: "we simply look at the total size (relative to the size of the input) of any new variables we're allocating." I have seen candidates get dinged for saying "O(1) space" after building a set that could hold every element. The qualifier is what makes you sound like you understand the tool instead of reciting it.

Example 3: recursive tree DFS

JS

Copy

function maxDepth(root) { if (!root) return 0; const left = maxDepth(root.left); const right = maxDepth(root.right); return 1 + Math.max(left, right); }

How to say it:

• "n is the number of nodes."
• "I visit each node once, so time is O(n)."
• "Space is not O(1) because recursion uses the call stack."
• "Worst-case space is O(n) for a skewed tree, and O(log n) for a balanced tree."

This is one of the most common places candidates forget space complexity. I bring this up in almost every coaching session because tree DFS is the problem where confident engineers say "O(1) space" and immediately lose credibility. The call stack is not free.

The trade-off language interviewers want

Complexity answers get stronger when they compare options instead of naming one number in isolation.

For a duplicate-check problem, a useful comparison is:

That is exactly how real interview follow-ups sound:

• "Can you improve the time?"
• "Can you reduce the space?"
• "Would your answer change if the array were already sorted?"

If you can compare solutions cleanly, you sound like someone making engineering choices instead of reciting a flashcard.

Mistakes that keep showing up

Forgetting the sort cost

I have seen this exact mistake in maybe thirty mocks. The candidate says a sort-and-scan solution is O(n) because the final scan is linear. It is not. The sort dominates, so the answer is usually O(n log n). The KDnuggets complexity cheat sheet is worth bookmarking — it puts sorting algorithm costs side by side so you stop treating .sort() as free.

Ignoring recursion or queue growth

DFS recursion, BFS queues, and monotonic stacks all consume space that can grow with the input. If the auxiliary structure grows, the space is not constant.

Using one variable for everything

Grids, graphs, and string-plus-pattern problems often have more than one input dimension. Say m and n when there are two meaningful sizes.

Mixing average and worst case carelessly

For interview purposes, "hash map operations are average O(1)" is a cleaner statement than just saying "O(1)" with no qualifier. Educative's Big-O course covers the amortized analysis behind this in detail. You do not need to prove it in the interview, but you do need to show you know the difference exists.

Explaining the code but not the growth

"I loop here, then I check a map, then I return" is not yet complexity analysis. You still need the sentence that connects repeated work to the final Big O.

A simple answer template

If you freeze under pressure, use this exact shape:

1. "n is ..."
2. "I do one pass / two nested passes / a sort plus one pass ..."
3. "So the time complexity is ..."
4. "The extra space is ... because ..."

Example:

"n is the number of elements in the array. I make one pass and use a hash set for membership checks, so the time complexity is O(n). The extra space is also O(n) because the set can store up to all elements."

That answer is short, precise, and interview-safe.

A 20-minute prep drill that pays off

Take eight classic patterns and force yourself to say time and space out loud:

• array scan
• nested loops
• binary search
• sorting plus sweep
• hash map or set
• tree DFS
• BFS with queue
• heap-based top-k

Do not just write the answer. Say it.

Most interview complexity misses are verbal misses, not conceptual misses. The candidate knew the answer but had never practiced stating it in one clean breath. GeeksforGeeks' top 30 Big-O interview questions is a good follow-up bank if you want to test whether you can actually answer the complexity questions interviewers ask, not just the ones you prepared for.

The real goal

You are not trying to sound like a textbook.

You are trying to show that when input size grows, you can predict where the cost comes from, explain the trade-off, and choose the version you would actually ship.

That is what Big O means in an interview.