Big-O for Interviews

Updated Nov 16, 2026 · 5 min read
On this page

    You write a solution, it passes the example, and the interviewer asks: "What happens when the list has a million items?" If your answer is a guess, the round stalls. Big-O is how you answer that question in one line, before running anything, and it is how you decide which idea is worth coding in the first place.

    How it works

    Count how work grows, not how long it takes

    Big-O describes how the number of steps grows as the input grows. It ignores constant factors and small terms, because for large inputs the shape of the growth is what decides whether code finishes in a second or in an hour.

    For small inputs every curve looks similar; as n grows, O(n²) and O(2ⁿ) leave the others far behind.
    For small inputs every curve looks similar; as n grows, O(n²) and O(2ⁿ) leave the others far behind.

    The classes you will meet in almost every interview, from fastest to slowest:

    ClassNameTypical code
    O(1)constanthash map lookup, array index, push and pop on a stack
    O(log n)logarithmicbinary search, one heap push or pop, balanced tree lookup
    O(n)linearone pass over the input
    O(n log n)linearithmicsorting, n heap operations
    O(n²)quadraticevery pair, nested loops over the same input
    O(2ⁿ)exponentialevery subset
    O(n!)factorialevery ordering

    Three rules cover most code

    1. Drop constants and small terms. Two passes over the input is O(2n), which is O(n). O(n² + n) is O(n²).
    2. Sequential work adds, nested work multiplies. A loop followed by another loop is O(n + m). A loop inside a loop is O(n · m).
    3. Halving gives a log. If each step throws away half of what is left (binary search, a balanced tree), the number of steps is about log₂ n. For a million items that's only about 20 steps.
    Two loops in a row add their costs; a loop inside another multiplies them.
    Two loops in a row add their costs; a loop inside another multiplies them.

    Space counts too

    Space complexity is the extra memory your code uses beyond the input. A hash map holding every element is O(n) space. A recursive function uses stack space equal to its depth, so a recursive DFS on a tree of height h is O(h) space even if you never allocate anything yourself. Say both numbers whenever you state a complexity: "O(n) time, O(n) space".

    Amortized cost

    Some operations are usually cheap and occasionally expensive. Appending to a dynamic array (a Python list, Java ArrayList, C++ vector, Go slice) is O(1) almost always, but every so often the array is full and must be copied to a bigger one, which is O(n). Because the array doubles each time, the copies are rare enough that the average cost per append stays O(1). This is called amortized O(1). Hash map inserts work the same way.

    Trade-offs and costs

    • Big-O hides constants. An O(n) solution that does heavy work per item can lose to an O(n log n) solution on realistic sizes. In interviews, Big-O is the main argument; mention constants only when two options are in the same class.
    • Average versus worst case. Hash map lookups are O(1) on average and O(n) in the worst case. Quicksort is O(n log n) on average and O(n²) in the worst case. Say which one you mean.
    • Time versus space. Most speed-ups spend memory: a hash map turns O(n²) into O(n) time but costs O(n) space. When the interviewer asks for O(1) extra space, the usual alternative is sorting plus two pointers.

    When to reach for it

    Before you code: read the limits

    The input limit tells you which complexity the interviewer expects, and that points to the technique.
    The input limit tells you which complexity the interviewer expects, and that points to the technique.

    A useful rule of thumb is that a typical machine does around 10⁸ simple steps per second, so a solution needs roughly n · (work per item) below that. Read the stated (or asked-for) input size and work backwards:

    • n up to about 12: you can afford to try every ordering.
    • n up to about 25: every subset is fine, which suggests backtracking or bitmasks.
    • n up to a few thousand: O(n²) is acceptable, so an all-pairs check or a 2D table works.
    • n up to about a million: you need O(n log n) or O(n), which points to sorting, a heap, a hash map or two pointers.
    • n up to a billion or more: you can't even read every value, so the answer is O(log n) or O(1): binary search or math.

    This is the fastest way to pick a pattern. If the interviewer says "the array can have 10⁵ elements", an O(n²) plan is already ruled out.

    After you code: state it in one line

    Finish every solution with "This is O(…) time because … and O(…) space because …". Interviewers expect it, and it often triggers the follow-up question they had planned.

    Example

    Find whether any two numbers in a list add up to a target.

    • Every pair: a loop inside a loop, so O(n²) time, O(1) space. With n = 10⁵ that is about 5 × 10⁹ pairs: too slow.
    • Sort, then two pointers from both ends: sorting is O(n log n), the scan is O(n), total O(n log n) time, O(1) extra space if you sort in place.
    • Hash set of numbers seen so far: one pass, O(1) per lookup, so O(n) time and O(n) space.

    The three answers trade time against space in a way you can explain in one sentence each. That comparison is exactly what the interviewer wants to hear.

    Common mistakes

    • Forgetting the cost of built-ins. x in list is O(n), not O(1). Slicing a list or a string copies it. list.pop(0) in Python is O(n); use a deque.
    • String building in a loop. Repeatedly doing s = s + c can copy the whole string each time, which is O(n²). Collect pieces in a list and join once.
    • Ignoring recursion depth. A recursive solution on a linked list or a skewed tree can be O(n) space and can overflow the stack.
    • Saying O(n) when two inputs differ in size. If you loop over two different arrays, use two letters: O(n + m), not O(n).
    • Counting sorting as free. If you sort, the whole solution is at least O(n log n).

    Say this in the interview

    • "The brute force is O(n²) because for each element I scan the rest. With n up to 10⁵ that's too slow, so I'm aiming for O(n log n) or better."
    • "Each element is pushed and popped from the stack at most once, so even though there's a loop inside the loop, the total work is O(n)."
    • "This is O(n) time and O(n) space for the hash map. If memory matters, I can sort and use two pointers for O(n log n) time and O(1) extra space."

    Used in

    Every problem article ends with a time and space line. Good next reads: Arrays and Strings, Hash Maps, and the Binary Search pattern, where the O(log n) idea comes from.