Big O notation for interviews: what it is and how to answer

In this article

1. Before you start
2. Why interviewers ask this
3. Big O notation from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is part of the coding interview questions guide, which covers the patterns and the method for the round.

Why interviewers ask this

After a solution is written, the next question is usually its cost: how does it behave when the input gets large? Candidates report being asked for the time and space complexity of their own code, so be ready to state both without prompting.

The question separates people who can read their own code from people who memorised a table. A weak answer says "it is O(n²)" with no reason, or says "big O is the worst case". A strong answer counts the loops, names the dominant term, says which case it describes, and states the extra memory. A Staff-level answer also says when the textbook cost is wrong: a hash lookup that degrades, a resize that is occasionally expensive, or a constant that matters at the real input size.

Big O notation from first principles

Big O notation

Big O notation is a way of writing an upper bound on how fast a function, such as the running time of an algorithm, grows with the input size n, ignoring constant multipliers and smaller terms, so that 3n² + 4n - 10 is written O(n²).

Big Theta

Big Theta is a tight bound that is both an upper bound (big O) and a lower bound (big Omega) on a function's growth, so Θ(g(n)) says g(n) describes the growth accurately for large n.

In plain words

Think of finding a name in a phone book. You can read every page from the front. Or you can open the middle, decide which half holds the name, and repeat. Both work. They grow differently when the book gets bigger. Doubling the pages doubles the first method's work. It adds only one more step to the second.

Big O captures that growth and drops the rest. The analogy breaks in one place. Real time depends on your computer, and big O ignores that on purpose.

In one precise sentence, f(n) = O(g(n)) says that g, multiplied by some constant, eventually stays above f.

Step 1: Count the steps as a function of n

Start by counting how many basic steps the code takes for an input of size n. A basic step is one comparison, one addition or one lookup. Loops one after another add their counts, so two O(n) loops in a row are still O(n); loops nested inside each other multiply, so two nested loops give O(n·n). Take a duplicate check with two nested loops.

def has_duplicate(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Input: a list of n items. Output: the number of comparisons. If there is no duplicate, every pair is compared once, which is n(n-1)/2 comparisons. For 1,000 items that is 499,500 comparisons.¹ The count is a function of n, and that function is what big O describes. You now have a formula to simplify, which Steps 2 and 3 do.

Step 2: Big O is an upper bound, and the case is a separate choice

An upper bound is a function that another function never exceeds, up to a constant, beyond some n. Formally, f(n) = O(g(n)) means there are a constant c > 0 and a starting point n0 such that f(n) ≤ c·g(n) for all n ≥ n0, the (c, n0) form used in the Jiménez notes; Lehman, Leighton and Meyer (2015) state an equivalent definition. The pair (c, n0) is a witness. For 3n² + 4n - 10 the witness pair is c equals 7 and n0 equals 1, because 3n² + 4n - 10 ≤ 7n² for every n from 1 up.¹

The "=" is a set-membership sign, not equality (Jiménez, course notes). Knuth (1976) defines O as a set of functions and notes that people had used it for lower bounds, a use the definition does not support.

The case is a different choice. Best, average and worst case are three functions, and each can be bounded. The Python documentation says that in the worst case, when every key hashes to the same value, each O(1) dictionary operation takes O(n) time. It also says sorted input takes only O(n) comparisons in sorting. So "worst case" names the case, and "O" names the kind of bound. Say both.

Step 3: Drop constants and low-order terms

Because only large n matters, the fastest-growing term decides the bound. The course notes simplify 3n² + 4n - 10 to O(n²), so 3n² + 4n - 10 is O(n²), and Cornell's lecture calls 10n³ + 24n² + 3n log n + 144 still cubic. At n = 1,000, the 3n² term is 3,000,000 of a total 3,003,990, which is 99.87% of the cost.¹

The constant 3 goes too. It changes the height of the curve and not its shape. A large constant still matters in practice, so measure at real sizes. A constant itself is O(1), including a huge one: the MIT notes say "Every constant is O(1)."

Watch the exponent. The same notes warn that 4^x = O(2^x) is incorrect, because 4^x is the square of 2^x. A constant that sits in an exponent changes the growth class, so it cannot be dropped.

Step 4: Read the common growth classes

The classes you will meet, from slowest to fastest growth, are O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ). O(1) means the cost does not depend on n. O(log n) appears when each step halves the remaining work, as in searching a sorted list by halving the range; the base of the logarithm does not change the class. O(n log n) is typical of efficient sorting.

Any constant, linear, quadratic or cubic algorithm is polynomial time, written n^O(1) (Cornell). O(2ⁿ) is not.

The usual matrix-multiplication algorithm is O(n³) in the worst case (MIT notes). With the four steps done, you can bound any simple piece of code. The worked example next puts numbers on the classes.

1 · Count the steps2 · Find a witness3 · Drop small terms4 · Rank the classesReplay

Step-by-step description

1. Write the work as a function of n.
2. A constant c and a start n0 show the upper bound holds.
3. Keep the fastest-growing term and drop the constant.
4. Compare the result with the common growth classes.

• 3n² + 4n - 10 is O(n²).
• The witness pair is c equals 7 and n0 equals 1.

Worked example

The duplicate check can be solved two ways. The nested loops above take n(n-1)/2 comparisons in the worst case, so they are O(n²) time and use O(1) extra space. The second way uses a hash set. A hash set is a collection that stores each value once and answers "is this value in here?" in constant time on average.

def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

This version does at most n lookups, so it is O(n) time on average with O(n) extra space. Set membership is O(1) on average and O(n) only if every key collides (Python docs). The nested loop makes n(n-1)/2 comparisons in the worst case: 45 at n = 10, 190 at 20, 780 at 40 and 3,160 at 80. The hash-set version does 10, 20, 40 and 80 lookups.¹ Doubling n roughly quadruples the nested loop (3,160 against 780 is a ratio of 4.05) and only doubles the other.¹

Text description of the diagram

• The nested loop makes n(n-1)/2 comparisons in the worst case.
• The hash-set version does at most n lookups.

For the nested loop at a million items, the comparison count is 499,999,500,000.¹ The hash set stays at a million lookups, at the price of memory for the stored values. That memory-for-time trade is why the answer to "what is the complexity" has two parts.

Trade-offs and edge cases

Big O is a rule of thumb. Cornell's notes point out that a linear algorithm with a huge constant can be worse in practice than an exponential algorithm with a small constant, and that the asymptotically best algorithm is not necessarily the best one. For small inputs, measure.

Space is counted with the same notation. Space complexity is the extra memory an algorithm allocates beyond its input, and the hash-set version above needs O(n) of it where the nested loop needs O(1). State both costs.

Library calls hide costs. Appending to a list is amortized O(1), and the table below shows five more operations. The Python documentation records that list.append is amortized O(1), because a resize is occasionally O(n) but is spread over many appends. It records that x in l on a list is O(n), that l.sort() is O(n log n) and O(n) on already-sorted input, and that key in d is O(1) on average.

Its list table gives insert and pop at index k as O(n - k), so index 0 is the worst spot: l.pop(0) shifts every other item, which is O(n). Membership in a list is O(n) but in a set it is O(1) on average. Building a string by concatenating many pieces in a loop can be quadratic in the total length (the docs say so; CPython sometimes avoids the copying, so do not rely on it), and collections.deque is the usual choice for operations at both ends of a sequence.

Text description of the diagram

• Appending to a list is amortized O(1).
• Membership in a list is O(n) but in a set it is O(1) on average.

The same reasoning explains familiar problems. Merge intervals costs O(n log n) because the sort dominates the linear sweep. Subarray sum equals k is linear on average because each dictionary step is O(1) on average. A monotonic stack is a standard amortized argument: each element is pushed and popped at most once. The longest substring without repeating characters solution shows a linear window pass, and K closest points to origin compares a sort with a heap.

How to answer it in an interview

The spoken structure: define the bound in one clause, count the loops, state time then space, name the case, and say the trade-off. More Python-specific cost questions are in the Python interview questions guide, and defaultdict in Python is built on the same dictionary costs.

Common mistakes

• "Big O is the worst case." (wrong) Big O is an upper bound on a function, and best, average and worst case are separate choices. (right) "In the worst case the running time is O(n²)."
• "This is O(n²), so it is exactly quadratic." (wrong) O gives only an upper bound. (right) "It is Θ(n²)" when you mean tight.
• "Dictionary lookup is always O(1)." (wrong) It is O(1) on average and O(n) if every key collides. (right) "O(1) on average."
• "list.append is always O(1)." (wrong) It is amortized O(1), and a resize is occasionally O(n). (right) "Amortized O(1)."
• "pop(0) on a list is cheap." (wrong) It moves the rest of the list and is O(n). (right) "I would use a deque for operations at the front."

Follow-up questions

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

Big O is an upper bound, big Omega is a lower bound, and Θ is both, so it is the tight bound (Jiménez, course notes). Knuth (1976) proposed the extra symbols because O was being misused for lower bounds.

Is big O the worst case?

No. The notation gives an upper bound and the case is a separate axis. You can state an O for the best, average or worst case of the same algorithm, as the Python docs do for hashing.

What is the time complexity of list append in Python?

Amortized O(1). An individual append may be O(n) when the storage is resized, but the cost is spread over many operations (Python docs).

What does amortized O(1) mean?

Amortized O(1) means the average cost per operation over a whole sequence is constant, even though one operation may occasionally be O(n). It is an average over operations in the sequence, so it differs from an average over random inputs.

How do you find the big O of a recursive function?

Count the calls, then multiply by the work done per call. Naive recursive Fibonacci calls itself twice for each value above 1, so the number of calls roughly doubles with each level of depth, and the running time is bounded above by O(2ⁿ). An upper bound of 2ⁿ is enough to state; you do not need the exact count.

What if the input has two sizes?

Give each size its own letter. For two lists of lengths n and m, one loop after the other is O(n + m), and a loop over one inside a loop over the other is O(n·m). Never collapse them into a single n, because the two sizes can differ greatly.

Sources

1. Big Omicron and big Omega and big Theta — ACM SIGACT News 8(2):18-24 (D. E. Knuth), 1 Apr 1976
2. Time complexity of operations on built-in types — Python Software Foundation (Python documentation), 26 Oct 2026
3. Analysis of Algorithms: Lecture 3, asymptotic notation — Daniel Jiménez, UTSA CS 3343 course notes, 26 Oct 2026
4. Mathematics for Computer Science, section 13.7 Asymptotic Notation — MIT OpenCourseWare 6.042J (Lehman, Leighton, Meyer), 18 May 2015
5. Lecture 16: Introduction to Asymptotic Analysis — Cornell CS312, 1 Sep 2004