27 Jun 2026 · Rehurz
Why Your O(n) Solution Isn't Passing the Interview
You solved the problem. Your code runs, produces the right output on every example, and your logic is sound. Then the interviewer asks: "What is the time complexity of that?" and something shifts. Getting complexity right in a time complexity interview is not about memorising formulas. It is about knowing why interviewers ask, what they are actually listening for, and how to communicate your analysis before and after you write a single line of code.
Quick answer: A correct solution can still fail a coding interview if its complexity does not fit the problem's constraints, or if you cannot explain why. Interviewers use Big-O notation to test whether you understand the performance envelope of your approach, not just whether it passes the visible examples. If you cannot analyze and articulate the complexity of your own code, that gap becomes the thing they remember. The sections below cover how to read complexity in common patterns, how to use input size as a guide, and how to state your analysis out loud in a way that lands well.
Why a Correct Solution Can Still Fail
Every interview problem carries hidden requirements alongside the visible ones: expected input size, latency tolerance, and the complexity bar the interviewer considers acceptable. A brute-force O(n^2) solution on n=10 works perfectly. The same code on n=10^6 times out, and the interviewer already knew that before you started.
When interviewers see an O(n^2) solution submitted without any acknowledgement of its complexity, they draw one of two conclusions: you do not know how to analyze your own code, or you know and did not bother to engage with it. Neither impression helps your candidacy.
The deeper point is that correctness is local and complexity is global. Does your code produce the right output for the given examples? Correctness. Does it scale to the full range of inputs the problem allows? That is what Big-O measures. Interviewers are often less focused on whether your first attempt is optimal and more focused on whether you can see what you wrote clearly enough to improve it.
What Big-O Notation Actually Measures
Big-O describes how the runtime (or memory usage) of an algorithm grows relative to input size as that input becomes large. You are measuring the rate of growth, not a time in milliseconds.
A few things worth being precise about, because interviewers do notice when candidates mix these up:
- Upper bound on growth. O(n) means the runtime grows at most linearly. It does not mean exactly n operations.
- Worst case by default. Unless the problem or interviewer specifies otherwise, assume worst-case analysis. Average case matters in specific discussions (quicksort is a classic example) and you should be able to name the distinction when asked.
- Constants are dropped. O(3n) simplifies to O(n). The coefficient depends on hardware and implementation, not on the algorithm's inherent growth rate.
- Lower-order terms are dropped. O(n^2 + n) is O(n^2). As n grows large, the dominant term swamps everything else.
Saying these things clearly in an interview is not showing off. It is demonstrating that you understand what the notation represents rather than applying a pattern you memorised.
How to Analyze Time Complexity in Common Patterns
Reading the complexity of your own code is a pattern-recognition skill. Here are the shapes that appear most often.
Single loop over n elements One pass through an array is O(n). This seems obvious, but check the loop body. A method call inside the loop that is itself O(n) makes the whole thing O(n^2). A sort inside a loop makes it O(n^2 log n). Look at every line inside the loop, not just the loop itself.
Nested loops
Two nested loops each running n iterations is O(n^2). Three nested: O(n^3). Watch the inner loop's range, though. A triangular pattern where the inner loop runs from i to n still gives O(n^2) total (roughly n^2 / 2 operations), which is the same complexity class, just with a better constant.
# O(n^2): inner loop runs from i to n each time
for i in range(n):
for j in range(i, n):
process(i, j)
Divide and conquer An algorithm that halves its input at each step and does O(n) work per level (merge sort, for example) runs in O(n log n). Binary search halves the search space each step and does O(1) work per step, giving O(log n).
Branching recursion A recursive function that calls itself twice with the full remaining input produces a call tree with 2^depth nodes. The textbook example is naive recursive Fibonacci: O(2^n). Drawing the recursion tree and counting nodes is the clearest way to see this.
Here is a growth comparison showing why the difference between these classes matters at realistic input sizes:
n O(n) O(n log n) O(n^2) O(2^n)
------- ------ ---------- ------ ------
10 10 33 100 1024
100 100 665 10,000 [huge]
1,000 1,000 9,966 1,000,000 [infeasible]
10,000 10,000 132,877 100,000,000 [infeasible]
The gap between O(n^2) and O(n log n) is not academic once n crosses a few thousand rows or elements.
Using Input Size to Target the Right Complexity
One of the most practical habits you can build is reading the input constraints before writing code and using them to decide what complexity you need. Here is a rough guide:
Input size (n) | Roughly feasible complexity
----------------+------------------------------
n <= 10 | O(n!), O(2^n)
n <= 20 | O(2^n), O(n^3)
n <= 500 | O(n^3)
n <= 5,000 | O(n^2)
n <= 100,000 | O(n log n)
n <= 1,000,000 | O(n) or O(n log n)
n > 10^8 | O(log n) or O(1)
This is not a rigid contract, but it is a working tool. When you see n up to 10^5 and you have written an O(n^2) solution, you already know it will likely time out before running a single test. The useful move is to say that out loud before submitting.
How to use this in the room: read the constraint, estimate the complexity you need, and pick your approach accordingly. Before you write a line, say it. "n can be up to 10^5, so I need something close to O(n log n). I will sort first and use a two-pointer pass rather than a nested loop." That single sentence demonstrates exactly the kind of reasoning interviewers are measuring.
Space-Complexity Tradeoffs
Runtime is not the only axis. Interviewers also ask about memory, particularly in problems where a naive O(n) space solution can be replaced by O(1) space at some cost to speed, or vice versa.
Hash map for O(1) lookups Trading O(n) extra space to reduce search from O(n) to O(1) per query. The classic two-sum problem goes from O(n^2) with a nested loop to O(n) with a hash map. The tradeoff is explicit: you use linear space to avoid quadratic time.
Sorting for structure Sorting costs O(n log n) time and O(1) to O(log n) extra space (depending on the sort algorithm), but unlocks binary search, two-pointer, and sliding window techniques that would not apply to an unsorted input.
Memoization Top-down dynamic programming stores subproblem results to avoid recomputation. The space cost is O(n) or O(n^2) depending on the state space, but it converts an exponential recursive tree to polynomial time.
When you make a tradeoff, name it explicitly. "I am using O(n) extra space here to keep the loop at O(n). If memory is tight, I could avoid the hash map and use sorting instead, but that brings the time cost to O(n log n)." Two sentences. That is what a complete answer sounds like.
Common Misjudgments That Cost Candidates Points
Hidden costs inside built-in operations
Methods that look cheap are sometimes not. In Python, checking if x in my_list is O(n) on a list and O(1) on a set. Slicing creates a copy, costing O(k) for a slice of length k. String concatenation in a loop in Python or Java builds intermediate objects and runs O(n^2) total. Know the data structures and string handling in the language you are using well enough to spot these.
Amortized vs. worst case Appending to a dynamic array (a Python list, a Java ArrayList) is O(1) amortized but O(n) in the single worst case when the internal array needs to resize. For most interview problems, amortized analysis is what matters. But if the interviewer asks specifically about worst-case performance per operation, you need to name the distinction. Knowing when to apply which framing is part of the depth being tested.
Call stack space in recursive solutions Recursive solutions carry an implicit O(depth) space cost for the call stack, separate from any data structures you create. A recursive binary search looks like O(1) space but is actually O(log n). A DFS on a tree uses O(h) space where h is the height, O(log n) for a balanced tree and O(n) for a completely skewed one. Omitting this when asked about space complexity is a common gap.
Big-O does not tell the whole story Two algorithms with the same Big-O class can differ substantially in practice because of constants, cache behavior, and input distributions. Saying "both approaches are O(n log n)" is accurate but a complete analysis would note whether one has a meaningfully better constant factor or behaves differently on the distribution of inputs the problem describes. This level of nuance is more relevant in senior-level interviews but worth being aware of.
Stating and Improving Complexity Out Loud
Analyzing complexity in your head and writing it as a comment is not enough. Interviewers want to hear the reasoning in real time. A pattern that works well:
- State the complexity before you finalize code. "I think this approach is O(n log n) because I am sorting first and then doing a single linear pass."
- Justify each component. "The sort is O(n log n). The loop after it is O(n). The combined complexity is O(n log n) since the sort dominates."
- Name the space cost. "I am using a hash map that holds at most n entries, so space is O(n)."
- Invite the challenge. "Does that fit the constraints here, or are you looking for something tighter?"
If the interviewer says your solution is too slow, do not panic. Ask what the expected constraint is if it was not stated. Then work backward from the table in your head: if n is 10^6, you need O(n) or O(n log n). Ask yourself which data structure or technique gets you there. Sorting, hashing, a sliding window, a monotonic stack: each one unlocks a class of problems.
This verbal reasoning pattern is its own skill, separate from knowing the theory. It needs practice under realistic conditions to become automatic.
Frequently Asked Questions
Is Big-O the same as time complexity? Big-O is the notation used to express time complexity (and space complexity). When people talk about a time complexity interview question, they mean: can you express how your algorithm's runtime grows as input size increases, and can you reason about whether that growth rate is appropriate for the problem?
How do you find the time complexity of a recursive function? Write the recurrence relation, then solve it. For a function that calls itself twice on half the input and does O(n) work per call, the relation is T(n) = 2T(n/2) + O(n), which solves to O(n log n) via the Master Theorem. For simpler cases, draw the recursion tree, count the total number of nodes, and multiply by the work per node. That gives the total time without needing to know the theorem by name.
What is the difference between amortized and worst-case complexity? Worst-case is the maximum time a single operation can take. Amortized complexity spreads the cost of occasional expensive operations over a long sequence, giving you the average cost per operation. Dynamic array insertion is O(n) in the single worst case (a resize), but O(1) amortized because resizes are rare. In most coding interviews, worst-case is the default assumption unless you note otherwise.
When should I worry about space complexity vs. time complexity? Always think about both, even if the interviewer only asked about one. State the space complexity after you state time. In interviews where memory is explicitly constrained (an embedded context, a streaming problem where you cannot hold the whole input), space complexity becomes the primary constraint. A candidate who volunteers both without being asked consistently reads as more thorough.
What if I cannot find a better solution than O(n^2)? Implement your O(n^2) solution clearly, state the complexity out loud, and explain what you would explore to improve it: sorting the input, using a hash set, applying binary search, or restructuring with a different data structure. Showing a direction for improvement is substantially better than ignoring the complexity question. Interviewers often care more about how you think under pressure than whether you reach the optimal solution in the time available.
Practising Complexity Analysis with Rehurz
Knowing Big-O on paper is different from explaining it under pressure while your code is visible and a skeptical interviewer is listening. That is the gap that deliberate practice closes, and it only closes if the practice mirrors the real conditions.
In Rehurz coding rounds, you explain your approach out loud before writing a line. The session cross-questions you on complexity and tradeoffs as you go: "What is the time complexity of this nested loop? Can you bring it down? What does that cost in space?" These follow-ups are not fixed questions from a bank. They adapt to what you actually said. After the round, you receive a written report scored on reasoning and correctness together, not just whether the tests pass. You can also see how the sessions work before committing. The first round is free, no card required. Start your first free coding round and practice stating and improving complexity the way a real interview demands it.
Your O(n) solution is not failing because it is wrong. It is failing because you have not shown that you understand why it is right, where it might break, and what you would do if it did. Complexity analysis is that conversation made explicit. The more fluent you are in it, the less the interview feels like a trap.