Learn · DSA · Foundations
Big-O Thinking
The one idea that lets you look at code and say “this will be fast” or “this will die” — before you ever run it. Every technical interview leans on this. It’s simpler than it looks.
Before we start
- What Big-O actually measures (and what it doesn’t)
- The 6 complexities that cover almost every interview
- How to look at code and name its Big-O on sight
- The two rules: drop constants, keep the dominant term
- Say “this is O(n²), here’s the O(n) version” out loud
- Know instantly if an approach will survive at scale
- Answer the interviewer’s favourite question: “can you do better?”
Why you’re learning it: Big-O is the language engineers use to talk about speed. In an interview, solving the problem is half; saying “my solution is O(n) time, O(1) space” is the other half. It’s also how you catch a slow idea before it costs you. ⏱️ ~25 min.
What is Big-O?
Big-O is not about seconds. It’s about how the work grows as the data grows. Two programs can both be “fast” on 10 items — the question is what happens at 10 million.
Picture finding a name in a phone book. Option A: start at page 1 and check every name — if the book doubles, your work doubles. That’s O(n). Option B: open the middle, decide left or right, and throw away half — every step halves what’s left. That’s O(log n), and it barely grows even for a giant book. Same task, wildly different growth. Big-O captures that shape.
The 6 complexities that matter
“Steps” below is roughly how much work at n = 1,000,000 items. Watch how fast the bad ones explode:
| Big-O | Nickname | Everyday example | Steps at n = 1M |
|---|---|---|---|
| O(1) | constant | Grab array[5] — one step, any size | 1 |
| O(log n) | halving | Binary search — halve the data each step | ~20 |
| O(n) | linear | Scan a list once | 1,000,000 |
| O(n log n) | good sort | Sorting done well | ~20,000,000 |
| O(n²) | every pair | A loop inside a loop | 1,000,000,000,000 |
| O(2ⁿ) | explosive | Try every combination | more than atoms in you |
This is the whole reason we “optimise”: at a million items, O(n) is a heartbeat and O(n²) is a trillion steps — the difference between instant and never.
How to name it by looking at code
You don’t compute anything — you count structure:
- No loop, direct access (return array[i]) →
O(1) - One loop over the data →
O(n) - A loop inside a loop (every pair) →
O(n²) - Halving the data each step (binary search) →
O(log n) - A hashmap lookup inside one loop → still
O(n)(the lookup is O(1))
Where you’ll use it — real life
Reconciling 80,000 records: the O(n²) “compare every pair” is 6.4 billion ops; the O(n) hashmap is 80,000. Big-O told you which to write before you wrote it.
“Can you do better?” always means “can you lower the Big-O?” Knowing this turns a scary question into a checklist.
A page that’s fine in testing but crawls in production is often an accidental O(n²) hiding in a nested loop.
Big-O also measures memory. A hashmap is O(n) space; two pointers can do the same job in O(1) space. Trade-offs live here.
The two rules
O(2n) and O(n + 100) are both just O(n). Big-O cares about the shape of growth, not the exact count.
O(n² + n) is O(n²) — at scale, the biggest term drowns the rest. Only the fastest-growing part matters.
Why we practice this
You won’t remember rules by reading them — you’ll own them by labelling real code. After a dozen snippets, naming the Big-O becomes automatic, which is exactly what the interview clock demands.
Now YOU do the reps
For each snippet, name the Big-O before opening the answer. Say why out loud.
A single for loop printing each item in a list of size n
O(n) — one pass, work grows in step with n.
Two nested for loops, each running n times
O(n²) — for every item you touch every item. This is the “every pair” shape.
Binary search on a sorted array — halve the range each step
O(log n) — halving means ~20 steps even at a million items.
Return the first element of an array
O(1) — direct access, no growth with size.
One loop over n, doing a hashmap .get() inside
O(n) — the loop is n, each lookup is O(1), so n × 1 = O(n).
Out loud, no notes: “What does Big-O measure, and why does O(n²) die at scale while O(n) survives?” Fluent = you own it. Then log it in your Journal.
Next on the roadmap: Two Pointers →