· Learn With Examples ·
Big O is not maths for its own sake. It is a one-line answer to the only question that matters when your data grows: does this code get a little slower, or does it fall off a cliff?
Here’s the moment Big O suddenly makes sense to people. I once watched a junior developer ship a feature that checked a list of orders for duplicates. It worked perfectly. Tests passed, code review passed, demo went beautifully. Three months later the same feature took nine minutes to load and brought a support queue to a standstill.
Nothing had changed in the code. The only thing that changed was the number of orders — from about 300 to about 40,000. His approach compared every order against every other order, so the work grew with the square of the list. Going 130 times bigger made it roughly 17,000 times slower.
Big O notation is how you spot that in advance, in about ten seconds, without running anything. It’s a shorthand for describing how the work an algorithm does grows as its input grows — and once you can read it, that nine-minute disaster becomes something you catch during code review instead of during an outage.
What Big O actually says
Big O describes the growth rate of an algorithm’s work as the input size n increases. It deliberately ignores hardware, programming language, and constant factors, because those change by a factor of two or ten — while growth rates change by a factor of millions.
O(1) means the input size doesn’t matter at all. O(log n) means work barely grows. O(n) means it grows in step. O(n²) means doubling the input quadruples the work. That last one is where systems die.
The idea in one picture
Everything else in this article is detail attached to this one shape. Watch what happens to each line as you move right along the horizontal axis — that axis is your data growing over the life of your product.
That bunching on the left is the trap. With 20 test records, an O(n²) function and an O(n) function both return instantly. There is no observable difference. The difference only exists at scale, which means you cannot discover it by testing on small data — you have to reason about it. That reasoning is what Big O gives you.
The classes, with examples you’ll recognise
There are only six you meet regularly. Tap through them — each one has a plain-English meaning, a real piece of code, and an everyday analogy that makes the growth rate obvious.
Complexity explorer
tap a classO(1) Constant time
The work never changes, no matter how big the input gets. Looking up one item takes the same time in a list of ten or ten million.
Real example: fetching a value from a dictionary or hash map, reading array[500], pushing onto a stack, checking whether a number is even.
Analogy: opening a specific page in a book when you already know the page number. The book’s thickness is irrelevant.
O(log n) Logarithmic time
Each step throws away half the remaining work. Doubling the input adds just one extra step — which is why this class stays fast at absurd scales.
Real example: binary search in a sorted array, finding a record in a balanced tree index, the depth of a database B-tree.
Analogy: the guessing game. “Is it higher or lower?” finds a number between 1 and a million in 20 guesses, because each guess halves the range.
Bars scaled to their own maximum — notice how the growth flattens out almost immediately.
O(n) Linear time
Work grows in lockstep with the input. Twice the data, twice the time. Perfectly respectable, and often unavoidable — if you must look at every item, you cannot beat linear.
Real example: finding the largest number in an unsorted list, counting words in a document, validating every row of a CSV.
Analogy: reading every name on a guest list to find one person. A list twice as long takes twice as long.
O(n log n) Linearithmic time
A linear pass repeated across a logarithmic number of levels. Slightly worse than linear, dramatically better than quadratic, and the practical ceiling for comparison-based sorting.
Real example: merge sort, quicksort on average, and every sort() in every standard library you have ever used.
Analogy: splitting a deck of cards in half repeatedly, then merging the piles back in order. You touch every card at each of about ten levels.
O(n²) Quadratic time
Every item is compared against every other item. Double the input and the work quadruples. This is the class that quietly kills features six months after launch.
Real example: the duplicate-checking loop from the opening story, bubble sort, comparing every pair of records to find matches, a nested loop over the same list.
Analogy: every guest at a party shaking hands with every other guest. Ten guests means 45 handshakes; a hundred guests means 4,950.
O(2ⁿ) Exponential time
Adding a single item doubles the work. Usable for tiny inputs and hopeless past roughly 40 items — at n = 60 you are past the age of the universe.
Real example: generating every possible subset, naive recursive Fibonacci, brute-forcing a password, solving the travelling salesman by trying every route.
Analogy: the grain-of-rice-on-a-chessboard story. Doubling per square sounds harmless until square 64 needs more rice than exists on Earth.
Why the difference is so violent
Abstract symbols don’t frighten anyone. Actual step counts do. Pick an input size below and look at how the same six classes behave on it.
Steps required, by input size
pick an n| Class | Typical operation | Steps for n = 10 | Time at 1 billion ops/sec |
|---|---|---|---|
| O(1) | Look up a key in a hash map | 1 | instant |
| O(log n) | Binary search a sorted list | 3 | instant |
| O(n) | Scan every item once | 10 | instant |
| O(n log n) | A good sort | 33 | instant |
| O(n²) | Compare every pair | 100 | instant |
| O(2ⁿ) | Try every subset | 1,024 | 1 microseconds |
| Class | Typical operation | Steps for n = 100 | Time at 1 billion ops/sec |
|---|---|---|---|
| O(1) | Look up a key in a hash map | 1 | instant |
| O(log n) | Binary search a sorted list | 7 | instant |
| O(n) | Scan every item once | 100 | instant |
| O(n log n) | A good sort | 664 | instant |
| O(n²) | Compare every pair | 10,000 | 10 microseconds |
| O(2ⁿ) | Try every subset | beyond counting | longer than the universe has existed |
| Class | Typical operation | Steps for n = 1,000 | Time at 1 billion ops/sec |
|---|---|---|---|
| O(1) | Look up a key in a hash map | 1 | instant |
| O(log n) | Binary search a sorted list | 10 | instant |
| O(n) | Scan every item once | 1,000 | 1 microseconds |
| O(n log n) | A good sort | 9,966 | 10 microseconds |
| O(n²) | Compare every pair | 1.0 million | 1 ms |
| O(2ⁿ) | Try every subset | beyond counting | longer than the universe has existed |
| Class | Typical operation | Steps for n = 1,000,000 | Time at 1 billion ops/sec |
|---|---|---|---|
| O(1) | Look up a key in a hash map | 1 | instant |
| O(log n) | Binary search a sorted list | 20 | instant |
| O(n) | Scan every item once | 1.0 million | 1 ms |
| O(n log n) | A good sort | 19.9 million | 20 ms |
| O(n²) | Compare every pair | 1 trillion | 17 minutes |
| O(2ⁿ) | Try every subset | beyond counting | longer than the universe has existed |
Swipe the table sideways on a narrow screen →
One billion operations per second is roughly a fast modern CPU doing simple work. The point is not the exact seconds — it is how violently the bottom two rows change as n grows.
Read across the O(n²) row as you switch sizes. At a thousand items it’s a million steps — a blink. At a million items it’s a trillion steps, and your feature is now a fifteen-minute job that times out. Nothing about the code changed. Only n did.
A faster computer buys you a constant factor. A better algorithm buys you a different curve. Only one of those scales.
The two rules that make Big O readable
Big O deliberately throws information away, and the two things it throws away trip up every beginner. Both rules exist for the same reason: at large n, only the fastest-growing part matters.
Rule 1 — drop the constants
An algorithm that does 3n + 12 operations is written O(n), not O(3n + 12). That looks like cheating, but consider: at a million items, 3n is three million and n² is a trillion. The constant 3 is noise beside that gap. And constants change anyway — a faster CPU, a better compiler, or a different language shifts them freely, while the shape of the curve does not.
Rule 2 — keep only the dominant term
An algorithm costing n² + 500n + 9000 is O(n²). At n = 10, the 500n part is actually bigger. At n = 10,000, the n² term is 100 million and the rest is five million — the square has swallowed everything. Big O describes where things end up, not where they start.
The honest caveat. Those discarded constants sometimes matter enormously in practice. An O(n log n) algorithm with a huge constant can lose to an O(n²) one on lists of thirty items — which is exactly why real sorting libraries switch to insertion sort for small chunks. Big O tells you what happens as data grows. It does not promise which is faster today, on your data, at your size.
How to find the Big O of code you’re looking at
You don’t need to count operations. Four patterns cover almost everything you’ll meet in ordinary application code.
| What you see | What it means | Result |
|---|---|---|
| Statements one after another | Costs add, then the biggest one wins | O(a) + O(b) → the larger of the two |
| A loop over the input | Body runs n times | n × cost of the body |
| A loop inside a loop | Costs multiply | Usually O(n²) |
| Input halves each step | Only log₂n steps possible | O(log n) |
Two things people get wrong constantly. First, two loops side by side are not quadratic — they’re n + n = 2n, which is linear. Nesting is what multiplies, not adjacency. Second, a loop with a fixed bound isn’t linear: looping 100 times regardless of input is constant work, because 100 doesn’t grow with n.
Five snippets — guess before you open
Read each one, decide, then open it. These are the shapes that actually appear in real code.
1. Checking a list for duplicates the obvious way
for i in range(len(orders)):
for j in range(i + 1, len(orders)):
if orders[i].id == orders[j].id:
flag(orders[i])O(n²) — a loop inside a loop over the same list. It runs about n²/2 times, and dropping the constant leaves n². This is the exact code from the opening story. The fix is a set: add each id to a set and check membership, turning it into O(n) with O(n) extra memory. Nine minutes becomes a fraction of a second.
2. Two loops, one after the other
for user in users:
send_welcome(user)
for user in users:
log_signup(user)O(n) — not O(n²). Sequential loops add: n + n = 2n, and the constant 2 gets dropped. Merging them into one loop makes the code twice as fast in wall-clock terms but leaves the complexity class unchanged. That distinction — real speedup, same Big O — is worth internalising.
3. Halving the search space
lo, hi = 0, len(sorted_items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sorted_items[mid] == target: return mid
if sorted_items[mid] < target: lo = mid + 1
else: hi = mid - 1O(log n) — binary search. Each pass discards half of what’s left, so a billion items takes about 30 passes. The catch is the precondition: the list must already be sorted, and sorting costs O(n log n). Sorting once to search many times is a great trade; sorting once to search once is not.
4. A nested loop that isn’t quadratic
for order in orders: # n orders
for tax in TAX_BANDS: # always 7 bands
apply(order, tax)O(n) — linear, despite the nesting. The inner loop’s length is fixed at 7 and never grows with the input, so the total is 7n, and the 7 is a constant. Nesting only multiplies complexity when both loops scale with the input. Judge by what grows, not by indentation.
5. The classic recursive trap
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2)O(2ⁿ) — each call spawns two more, so the call tree roughly doubles at every level. fib(30) makes about 1.6 million calls; fib(50) would run for days. Caching results (memoisation) collapses it to O(n), because each value is then computed exactly once. Same algorithm on paper, a difference of billions in practice.
Best, average and worst case
One algorithm can have three different complexities depending on what you feed it. Searching an unsorted list for a name: if it’s first, you’re done in one step; if it’s last or missing, you check all n.
Best case
The luckiest possible input. Mostly useless for planning — nobody guarantees you luck.
Average case
What typical data does. The most honest number for everyday performance work.
Worst case
The input designed to hurt you. This is what Big O usually reports, and what you should plan around.
The default assumption when someone says “this is O(n log n)” is worst case, unless they say otherwise. That’s deliberately pessimistic, and it’s the right default: your worst case will eventually arrive, and it tends to arrive at the busiest moment. Quicksort is the cautionary tale — O(n log n) on average, O(n²) when the pivots go badly, and the input that triggers it is the very ordinary case of already-sorted data.
Space complexity counts too
Big O describes memory as readily as time. An in-place sort uses O(1) extra space; merge sort needs a scratch array, so O(n). The duplicate-checking fix above trades memory for speed — building a set of every id costs O(n) space to save you from O(n²) time. That trade is almost always worth taking, and recognising when it’s available is most of practical optimisation.
Where this actually matters
Code review
Spotting a nested loop over two growing collections takes seconds and prevents the outage three months later.
Choosing data structures
Array lookup by index is O(1); searching an array is O(n); a hash map turns that search into O(1). Most real speedups are structure changes, not clever code.
Database work
An index converts an O(n) table scan into an O(log n) lookup. That’s the whole reason indexes exist.
Interviews
“What’s the complexity?” is asked in nearly every technical interview, and the follow-up is always “can you do better?”
Don’t over-apply it. If your list has 50 items and always will, an O(n²) loop is completely fine and probably clearer to read. Big O matters when n can grow — and the real skill is asking “how big can this get?” before optimising anything. Most performance work is wasted on code that was never going to be the bottleneck.
Check yourself
Five questions. Open each to check — the correct option is marked.
1. An algorithm takes 4n + 200 steps. What is its Big O?
- O(4n + 200)
- O(n)
- O(200)
- O(n²)
Drop constants and lower-order terms — only the growth rate survives, and this one grows linearly.
2. Two separate loops over the same list of n items. Total complexity?
- O(n²)
- O(n)
- O(2n²)
- O(log n)
Sequential loops add — n + n = 2n, which is O(n). Only nested loops multiply.
3. Which class describes binary search on a sorted array?
- O(1)
- O(log n)
- O(n)
- O(n log n)
Each comparison eliminates half the remaining candidates, so a billion items needs only about 30 steps.
4. Your O(n²) function handles 1,000 records in one second. Roughly how long for 10,000?
- 10 seconds
- About 100 seconds
- 1 second
- 3 seconds
Ten times the input means a hundred times the work, because the growth is quadratic. This is the calculation to do before shipping, not after.
5. You replace a nested-loop duplicate check with a hash set. What changed?
- Time O(n²) → O(n), memory unchanged
- Time O(n²) → O(n), memory O(1) → O(n)
- Nothing changes
- Time gets worse, memory improves
You bought a much better time complexity by spending memory on the set. Recognising that trade is most of practical optimisation.
Frequently asked questions
What is Big O notation in simple terms?
It’s a shorthand for how an algorithm’s work grows as its input grows. O(n) means the work grows in step with the data; O(n²) means doubling the data quadruples the work. It describes the shape of that growth, not a measurement in seconds.
Why do we ignore constants in Big O?
Because constants depend on hardware, language and compiler, and they change by small factors — while growth rates change by factors of millions. At a million items the difference between 3n and n is trivial; the difference between n and n² is a trillion steps.
Is O(1) always faster than O(n)?
Not necessarily at small sizes. A constant-time operation with heavy overhead can lose to a linear scan of ten items. Big O describes behaviour as n grows large, so it’s a statement about trends, not a guarantee about any particular input.
What’s a good Big O to aim for?
O(1) and O(log n) are excellent, O(n) is usually fine and often unavoidable, O(n log n) is the practical target for sorting. Treat O(n²) as a warning sign worth investigating, and anything exponential as unusable beyond tiny inputs.
Do I need Big O if I’m not doing interviews?
Yes, though you’ll use it informally. You don’t need the formal maths, but you do need the instinct that says “this loop is inside that loop, and both grow with the data” — that instinct is what stops a working feature becoming an outage once real data arrives.
The takeaway
Big O answers one question: as your data grows, does this code degrade gently or catastrophically? O(1) and O(log n) barely notice. O(n) and O(n log n) scale honestly. O(n²) and worse are fine on toy data and fatal on real data.
You don’t need to derive it formally. You need to look at a function and ask two questions: what grows here, and is anything nested inside anything else that also grows? That habit catches the overwhelming majority of real performance problems, long before they reach production.
Try it on something you wrote this week. Find your longest loop, ask what its input can realistically grow to, and check whether anything scaling sits inside it. That’s the whole practice — and it takes about thirty seconds once the six shapes above are familiar.
big o notationtime complexityalgorithmsspace complexityperformancecomputer science
