Big-O notation answers one question: when the input gets bigger, how fast does the cost grow? It doesn’t tell you how many milliseconds a function takes on your laptop. An O(n) function written carelessly can be slower than an O(n²) one at n = 10. What Big-O promises is the shape of the curve, and at the input sizes interviews care about (thousands to millions of items), the shape wins.
The fastest way to build intuition is to stop thinking about formulas and start doubling the input.
Doubling n and watching the ratio
Take a classic problem, Contains Duplicate: return whether any value appears twice. Two obvious solutions:
def has_duplicate_nested(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
def has_duplicate_set(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return FalseThe real test added a step counter to each loop body and timed both on shuffled lists with no duplicates (the worst case, since neither can exit early). This is the output from Python 3.14 on an M1 MacBook Pro. Your milliseconds will differ; the ratios won’t.
n nested steps nested ms set steps set ms
1000 499,500 16.8 1,000 0.05
2000 1,999,000 63.3 2,000 0.11
4000 7,998,000 250.4 4,000 0.17
8000 31,996,000 1001.7 8,000 0.36Read it row by row. Each time n doubles, the nested version does four times the steps and takes roughly four times as long: 16.8 ms, 63.3 ms, 250.4 ms, a full second. That factor of four is the signature of O(n²). The set version’s steps double with n, which is the signature of O(n). At 8,000 items the gap is already a factor of nearly 3,000, and at a million items the nested version would run for hours.
The exact step count for the nested loop is n(n - 1) / 2, which is 499,500 for n = 1,000. Big-O throws away the 1/2 and the - n term because neither changes how the curve bends. If someone asks why constants are dropped, that’s the honest reason: doubling n multiplies n²/2 by four, the same as it multiplies n².
A third solution sorts first and compares neighbours. Sorting costs O(n log n), the scan costs O(n), and the larger term wins, so the whole thing is O(n log n). It sits between the other two, and it’s the right choice if you’re told you can’t use extra memory for a set.
Give every input its own letter
A common slip is calling every two-loop function O(n²). Suppose you check each of 1,000,000 log lines against a list of 50 banned IP addresses:
def flag_lines(lines, banned):
flagged = []
for line in lines: # n lines
for ip in banned: # m banned addresses
if ip in line:
flagged.append(line)
break
return flaggedThe cost is O(n · m), about 50 million substring checks in the worst case, not a trillion. Calling it O(n²) would claim that doubling the banned list is as expensive as doubling the log, which isn’t true. Interviewers listen for this: if two collections can grow independently, name them separately and keep both in the answer.
The same goes for strings inside collections. Sorting n words of length up to k costs O(k · n log n), because each comparison can touch up to k characters. That’s why Group Anagrams solutions that sort every word are O(n · k log k), and solutions that count letters instead are O(n · k).
Hidden linear work inside one line
Many complexity mistakes come from treating every line of code as constant time. Some lines quietly loop over a whole collection:
x in some_listscans the list:O(n). The same expression on a set or dict isO(1)on average.some_list.pop(0)andsome_list.insert(0, x)shift every other element:O(n).s[a:b]andlist(items)copy:O(length of the copy).result = result + pieceinside a loop builds a new string each time:O(n²)overall. Collect pieces in a list and"".jointhem once.
Here’s what pop(0) does to a queue that’s drained completely, compared with collections.deque, which removes from the front in constant time:
from collections import deque
items = list(range(n))
while items:
items.pop(0) # shifts the remaining n - 1 items left
q = deque(range(n))
while q:
q.popleft() # O(1)n= 50,000: list.pop(0) 192.6 ms deque.popleft() 2.0 ms
n=100,000: list.pop(0) 770.9 ms deque.popleft() 4.0 ms
n=200,000: list.pop(0) 3092.0 ms deque.popleft() 8.3 msThe list version quadruples each time n doubles: a loop of n iterations, each doing O(n) work. This exact bug turns a correct O(V + E) breadth-first search into something quadratic, and it’s easy to miss because the BFS code itself looks fine.
Worst case, average case and amortized
When you say a hash set lookup is O(1), you mean on average, assuming a decent hash function. If every key collided into one bucket, lookups would degrade to O(n). It’s fine to quote O(1) in an interview; it’s better to add “expected” or “average” so it’s clear you know the difference.
Amortized cost is a different idea. Appending to a Python list (or a JavaScript array, or a Java ArrayList) is O(1) amortized: most appends write into spare capacity, and occasionally the array is full and everything is copied into a bigger block. You can watch the resizes happen with sys.getsizeof:
import sys
lst, last, resizes = [], sys.getsizeof([]), []
for i in range(64):
lst.append(i)
size = sys.getsizeof(lst)
if size != last:
resizes.append(len(lst))
last = size
print("list resized when length reached:", resizes)list resized when length reached: [1, 5, 9, 17, 25, 33, 41, 53]Out of 64 appends only eight triggered a reallocation. Because capacity grows in proportion to the current size, the total copying across n appends stays proportional to n, so the average per append is constant even though an individual append can be O(n). “Amortized” is a promise about a sequence of operations, not about any single one. Average case, by contrast, is a statement about typical inputs.
Where log n comes from
A logarithm shows up whenever each step cuts the remaining problem by a constant fraction. Binary search over 1,000,000 sorted items needs at most 20 comparisons, because halving a million twenty times gets you below one. A balanced binary tree with a million nodes is about 20 levels deep. Doubling the input adds one more step. That’s why O(log n) operations feel free and why O(n log n) sorting is barely more expensive than a single pass.
The reverse pattern also gives a log: a loop that starts at j = 1 and doubles j until it reaches n runs about log₂ n times. Put that inside a loop over n items and you get O(n log n). Running it for n = 1,000 counted exactly 10,000 steps, against n · log₂ n ≈ 9,966.
Interview practice: the shrinking loop
A candidate looks at this function and says it’s O(n log n), because the outer loop runs log n times and the inner loop runs up to n times. Are they right?
def mystery(n):
steps = 0
i = n
while i > 0:
for _ in range(i):
steps += 1
i //= 2
return stepsAnswer
No, it’s O(n). Multiplying “number of outer iterations” by “maximum inner iterations” gives an upper bound, but not a tight one here, because the inner loop shrinks every round. Add up the actual work instead: n + n/2 + n/4 + .... That geometric series never reaches 2n, so the total is linear.
Running it confirms the count stays just under 2n:
n= 1,000: mystery= 1,994
n=1,000,000: mystery=1,999,993For a million, the count is 1,999,993, not the roughly 20 million that n log n would predict. The general habit to show in an interview: when loop bounds depend on each other, sum the work per iteration rather than multiplying the extremes. The same reasoning explains why building a binary heap from an array is O(n) and why the analysis of a dynamic array’s resizes comes out linear.
Further reading
- Data Structures and Algorithms interview questions
- DSA multiple-choice questions
- Algorithm Space Complexity and Auxiliary Storage, the memory half of the same analysis
- Hash Maps for Frequency and Membership Problems, where most
O(n²)toO(n)improvements come from - MIT 6.006 Introduction to Algorithms (Spring 2020): lecture 1 (Algorithms and Computation) and lecture 2 (Data Structures and Dynamic Arrays) cover this material