Growth, not stopwatch time
The first thing to unlearn is the idea that Big O measures speed in seconds. It doesn't. A modern laptop and a decade-old phone will finish the same loop at very different wall-clock times, yet both scale identically as the input grows. Big O throws away hardware, language, and constant factors and keeps only one thing: the shape of the curve that relates input size to work done.
That focus on shape is what makes it useful. An O(n) algorithm might actually be slower than an O(n^2) one on a handful of items, but as the input gets large the O(n) approach pulls away and never looks back. Big O answers the question that matters for real systems: when the data gets ten or a thousand times bigger, does the cost grow gently or explode? These curves are much easier to feel when you watch them diverge step by step rather than read them as formulas.
The complexity classes you'll actually name
A small vocabulary covers most interviews. O(1) constant time does a fixed amount of work no matter the input — indexing an array or an average hash lookup. O(log n) logarithmic time halves the problem each step, like binary search on a sorted array. O(n) linear time makes one pass over n items. O(n log n) linearithmic time is the cost of efficient comparison sorts such as merge sort and heapsort, and it's the practical floor for general-purpose sorting.
Higher up the curve, things get expensive fast. O(n^2) quadratic time comes from a loop nested inside another loop over the same data — a naive all-pairs comparison. O(2^n) exponential time shows up when you enumerate every subset or write naive recursive Fibonacci that re-solves the same subproblems; adding a single element roughly doubles the work. Recognizing which class your code falls into, and which line or recursive branch drives it, is the core skill.
How to read Big O precisely
To read Big O, keep only the fastest-growing term and drop constant multipliers. A loop doing 3n + 5 operations is O(n); a function running in n^2 + n steps is O(n^2), because for large n the n^2 term dwarfs everything else. That is why O(n) and O(500n) are the same class — Big O describes the shape of the growth curve, not a precise operation count.
Formally, Big O is an asymptotic upper bound: f(n) = O(g(n)) means f eventually stays below some constant multiple of g. In interviews people usually apply it to the worst case, but you can describe any case. When the growth is bounded both above and below by g, the tight bound is Big Theta, and Big Omega is the lower bound — worth knowing by name even though 'Big O' is the phrase everyone uses day to day.
def has_duplicate(nums):
"""Return True if any value appears more than once."""
seen = set()
for n in nums: # runs at most len(nums) times -> O(n)
if n in seen: # set membership is O(1) on average
return True
seen.add(n)
return False
# Brute-force alternative, shown for contrast:
# for i in range(len(nums)):
# for j in range(i + 1, len(nums)): # nested loop -> O(n^2)
# if nums[i] == nums[j]:
# return TrueBest case is O(1) when a duplicate appears at the start and we return early. Set membership is O(1) on average but degrades to O(n) under pathological hash collisions, so the strict worst case is technically O(n^2).
When to use it
- Comparing two candidate approaches before you write code — Big O tells you which one scales to the input sizes you expect.
- Checking whether a brute-force solution will pass the constraints (e.g. n up to 10^5 usually rules out an O(n^2) approach).
- Explaining and justifying your solution's efficiency out loud in a coding interview.
- Diagnosing why code runs fine on small test cases but crawls on large inputs.
Watch out for
- Confusing Big O with real-world speed. It ignores constant factors and small inputs, so an O(n log n) algorithm can genuinely lose to an O(n^2) one when n is tiny.
- Missing hidden costs. Slicing a list, copying an array, or concatenating strings inside a loop can quietly add a factor of n you didn't account for.
- Assuming hash-map and set operations are always O(1). They're O(1) on average, but collisions or bad key distributions can push them to O(n) in the worst case — and ignoring space complexity entirely is just as common a slip.
Almost every coding interview touches Big O. After you sketch a solution, interviewers routinely ask "What's the time and space complexity?" and they're listening for whether you can identify the dominant term, point to the specific loop or recursive branch that drives the cost, and reason about trade-offs — for example, spending O(n) memory on a hash set to cut time from O(n^2) to O(n). Strong candidates state complexity in terms of the actual input variables (n and m, or the number of nodes and edges), call out best versus worst case when it matters, and don't over-claim O(1) for operations that are only O(1) on average. Getting the shape of the growth right, and being able to defend it, matters far more than reciting a memorized table.