Let's start with a very simple situation.
Two friends solve the same assignment: check whether any two students in the college share a birthday. Both programs are correct. On their class list of 60 students, both finish instantly. Then someone runs the same two programs on the full university database — 2 lakh students. One answers in a blink. The other is still running when the canteen closes.
Same machine. Same language. Same correct answer. So what exactly is different?
That question is this entire lesson. By the end of it, you will be able to look at a piece of code — before running it — and predict whether it will survive 2 lakh inputs. That skill has a name: reading time complexity.
First, let's understand the problem
Here is what we actually want: a way to compare two solutions before the exam-day input arrives. Not "which felt faster on my laptop" — a way to say, with confidence, "this one will still be fine at 2 lakh students, and that one will not."
What would we naturally do? Run both programs and time them with a stopwatch. Perfectly reasonable first idea. Let's see why it isn't enough.
Why can't we just measure seconds?
Try this thought experiment. You time your program: 2 seconds. Your friend times the same program on her laptop: 5 seconds. Is your code better than hers? Obviously not — it's the same code. Now you close 40 Chrome tabs and run it again: 1.2 seconds. Did your algorithm improve? No — your laptop just breathed easier.
Seconds measure the machine as much as the code. We need a measurement that belongs to the algorithm alone.
Pause for a second — what could that measurement be?
Here is the idea: instead of asking "how many seconds?", ask "how many steps?" A step is one basic operation — a comparison, an addition, reading one array element. Steps don't care whose laptop is running. And one more upgrade: we don't even care about the exact step count. We care about one thing only:
If the input becomes 10 times bigger, how much more work does the code do?
Counting steps: the two birthday programs
Let's apply that question to the two friends. Start tiny — 4 students, birthdays [j, m, j, d] (j = January and so on).
Program 1 — the natural approach. Compare every student with every other student:
def has_shared_birthday(birthdays):
n = len(birthdays)
for i in range(n):
for j in range(i + 1, n): # every PAIR
if birthdays[i] == birthdays[j]:
return True
return FalseFor 4 students, the pairs are (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) — 6 comparisons. Fine. Now let's ask the question that matters: how does this grow?
students pairs to compare 4 6 60 1,770 1,000 ~5 lakh 2,00,000 ~2,000 crore
Do you see what happened? The input grew about 3,000 times (60 → 2 lakh), but the work grew about 1 crore times. The number of pairs is n × (n−1) / 2 — when n doubles, the pairs roughly quadruple. This is the friend whose program never finished.
Program 2 — a different idea. Sort the birthdays first, then walk once: any shared birthday must now be sitting next to its twin.
def has_shared_birthday(birthdays):
birthdays.sort() # ~ n log n steps
for i in range(len(birthdays) - 1): # one pass: n steps
if birthdays[i] == birthdays[i + 1]:
return True
return FalseFor 2 lakh students: sorting takes roughly 2,00,000 × 18 ≈ 36 lakh steps, and the walk takes 2 lakh more. Under 40 lakh steps total — versus 2,000 crore. That is the difference between the two friends, and notice: we found it without a stopwatch, without even running the code. We counted growth.
The observation that gives us Big-O
Now the key observation. When we compared the two programs, the exact numbers (6 pairs, 1,770 pairs) didn't matter. What mattered was the shape of the growth: one program's work grew like n², the other's like n log n.
Big-O notation is simply a short name for that shape. We write O(n²) for "grows like n squared", O(n) for "grows in proportion to n", O(1) for "doesn't grow at all". Two cleanup rules make the names tidy, and both follow from caring only about the shape:
Rule 1 — drop constant multipliers. 3n steps and n steps are both O(n). "But 3n is three times slower!" — true, and at any realistic size that factor of 3 is survivable. What kills programs is the curve bending upward, and 3n bends exactly like n. Big-O deliberately ignores what a faster laptop can fix, and keeps what it can't.
Rule 2 — keep only the biggest term. n² + 5n + 20 is just O(n²). Check it yourself at n = 1,000: n² is 10,00,000 while 5n is 5,000 — the smaller terms are pocket change riding along with a crorepati.
The ladder, with real numbers
Every algorithm you will meet in this course lands on one of six rungs. Here they are — and this diagram plus this table are worth more than any definition:
| Label | Name | Steps at n = 1,000 | Steps at n = 1 lakh | Classic example |
|---|---|---|---|---|
| O(1) | constant | 1 | 1 | array index, dict lookup |
| O(log n) | logarithmic | 10 | 17 | binary search |
| O(n) | linear | 1,000 | 1,00,000 | one scan of a list |
| O(n log n) | linearithmic | ~10,000 | ~17 lakh | good sorting |
| O(n²) | quadratic | 10 lakh | 1,000 crore | all pairs, nested loops |
| O(2ⁿ) | exponential | astronomical | forget it | trying every subset |
One more number, and the whole table turns into a clock: a normal machine does roughly 10 crore (10⁸) simple operations per second. So O(n²) at n = 1 lakh ≈ 1,000 crore operations ≈ 100 seconds. O(n log n) at the same n ≈ 17 lakh operations ≈ done before your finger leaves the Enter key.
"Wait — what is this log n thing, really?" Fair question, because it's the strangest rung. log₂ n just answers: how many times can I cut n in half before reaching 1? Try it: 8 → 4 → 2 → 1 is 3 halvings, and log₂ 8 = 3. Now feel the power: 1 lakh needs only 17 halvings. 10 lakh needs 20. Whenever an algorithm throws away half the remaining work each step, its cost is log n — that's binary search and balanced trees, coming later in this course.
Dry run: reading complexity off code
Good news: you almost never calculate complexity with formulas. You read it off the code's shape, using three rules. Let's derive each one from a tiny example instead of memorising it.
Shape 1 — one pass.
total = 0
for price in prices: # n items
total += price # 1 step eachn items, constant work per item → n steps → O(n). Nothing to derive; count what you see.
Shape 2 — a loop inside a loop.
for i in range(n):
for j in range(n):
compare(arr[i], arr[j])Pause — before reading on, how many times does compare run for n = 4?
For every one of the n outer turns, the inner loop runs n times: n × n = 16 for n = 4. Nesting multiplies → O(n²). And a subtle variant you saw in Program 1: the inner loop started at i + 1, so it shrinks each time. Does that save us? Count it: (n−1) + (n−2) + ... + 1 = n(n−1)/2. At n = 1,000 that is ~5 lakh instead of 10 lakh — half the work, same shape. The ÷2 is a constant, and Rule 1 drops it: still O(n²).
Shape 3 — two loops one after another.
for x in arr: # n steps
...
for x in arr: # n more steps
..."Two loops — so n², right?" This is the single most common mistake in this topic, so let's kill it carefully. The second loop does NOT run once per iteration of the first — it runs after the first finishes. n + n = 2n → drop the 2 → O(n). The test is simple: is the loop inside the other (multiply) or after it (add)?
Shape 4 — halving.
i = n
while i > 1:
i = i // 2 # half the work disappears each turnWe already know this one: halving until 1 is log₂ n turns → O(log n).
That's the whole toolkit: sequence adds, nesting multiplies, halving is log. Ninety percent of every complexity question you will ever face is these three rules applied calmly.
What if...? (best case, worst case, hidden costs)
Time to stress-test our new skill, because interviews live in the corners.
What if the answer is found immediately? Say you scan a list for a value and it sits at position 0 — one step! Is linear search O(1) then? That was the best case, and nobody plans around best cases — that's like planning your monthly budget assuming you win a lucky draw. When someone says "complexity" with no qualifier, they mean the worst case: the input arranged as badly as possible. For linear search, the value is at the end or absent — O(n).
What if average and worst differ a lot? Then say both — that's not indecision, it's precision. The most famous example is coming in lesson 5: hash table lookup is O(1) on average and O(n) in the worst case, and the complete answer names both plus when the worst one bites.
What if a loop runs a fixed number of times? A loop over the 26 letters of the alphabet, inside a loop over n words — O(26n)? The 26 never grows with the input, so it's a constant: O(n). A bound that cannot grow is not an n.
What if n is small? Then honestly, none of this matters much — at n = 100, an O(n²) solution does 10,000 steps and finishes instantly. Big-O is a promise about large inputs. Knowing when the machinery is overkill is part of knowing the machinery.
Memory is part of the story
The same growth question applies to memory: how much extra space does the algorithm need as n grows? (Extra — the input itself doesn't count.) Three quick calibration points:
Reversing an array by swapping its two ends inward uses two index variables, whatever the size → O(1) extra space. Building a set of already-seen values to catch duplicates → the set can grow as big as the input → O(n) extra.
And one that surprises everyone the first time:
def countdown(n):
if n == 0:
return
countdown(n - 1)
countdown(100000) # RecursionError!No list, no set — where did the memory go? Every unfinished function call keeps a frame alive in memory, and countdown(100000) has one lakh unfinished calls stacked up at its deepest moment. Recursion costs O(depth) space even when it creates no data at all. Keep this in your pocket — it returns in the recursion lesson with a full picture of that stack.
Notice, finally, that Program 2's set-based cousin (store birthdays in a set, ask "seen before?") buys O(n) time by spending O(n) memory. Time and space often trade against each other, and naming the trade out loud — "we gain speed, we pay memory" — is what a strong answer sounds like. You'll do it in every lesson of this course.
Common mistakes
- Writing O(2n) or O(n/2) — constants are always dropped; both are O(n).
- Multiplying sequential loops. Two separate O(n) loops are O(n), not O(n²) — inside multiplies, after adds.
- Reporting the best case when asked for "the" complexity — the default meaning is worst case.
- Forgetting recursion's hidden stack when asked about space — "no lists created" does not mean O(1).
- Treating a fixed-bound loop (26 letters, 12 months) as O(n) — a bound that never grows is a constant.
- Using Big-O as a stopwatch for small inputs — it describes growth, and small-n verdicts can flip.
How do I use this in interviews?
Three concrete habits, all cheap:
1. Every solution ends with one breath of complexity. "One pass, constant work per element — O(n) time, O(1) space." Interviewers ask "what's the complexity?" after every single coding question; answering before they ask is a free mark.
2. Read the constraints line first. If the problem says n ≤ 10⁵, the setter is telling you O(n²) (10¹⁰ steps ≈ 100 seconds) will not pass — so an O(n log n) or O(n) idea is expected. The constraint is a hint hiding in plain sight.
3. When you optimise, say what you removed. "The nested loop was re-checking pairs; the set remembers what we've seen, so each element is handled once." Naming the eliminated waste shows you understand why it's faster, not just that it is.
Quick revision
| Concept | One-liner |
|---|---|
| Big-O | how work grows with input size — shape, not stopwatch |
| The ladder | 1 < log n < n < n log n < n² < 2ⁿ |
| Reading code | sequence adds, nesting multiplies, halving is log |
| Default meaning | worst case; name the average too when they differ |
| Space | extra memory as n grows; recursion costs O(depth) |
| The clock | ~10⁸ simple operations per second — Big-O into seconds |
One thing to remember
Don't ask "how fast is this code?" Ask "what happens to the work when the input gets 10× bigger?" Every complexity question — in this course, in interviews, in real systems — is that one question wearing different clothes.
Practice Zone — PYQs from real selection rounds
Six MCQs, then two hands-on tasks. Attempt each one before revealing — and if you get one wrong, the explanation tells you which rule you slipped on.
What does O(n) actually promise about an algorithm?
Asked in
What is the time complexity of this code?
for i in range(n): for j in range(n): print(i, j)
Asked in
A loop halves the remaining input each step until one element is left. Its complexity is:
Asked in
Two separate (not nested) loops each run n times. The total complexity is:
Asked in
Which ordering is correct from fastest-growing (worst) to slowest-growing (best)?
Asked in
A recursive function computes factorial(n) with one recursive call per level and no arrays. Its SPACE complexity is:
Asked in
Hands-on tasks:
State the time complexity of each snippet, with one line of reasoning each. Answer before revealing.
Asked in
# Snippet A
total = 0
for x in arr: # arr has n items
total += x
# Snippet B
for i in range(n):
for j in range(i + 1, n):
compare(arr[i], arr[j])
# Snippet C
i = n
while i > 1:
i = i // 2Both functions check whether a list contains a duplicate. Give the time complexity of each, and say which one you would ship for n = 10,00,000.
Asked in
def has_dup_v1(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False
def has_dup_v2(arr):
seen = set()
for x in arr:
if x in seen:
return True
seen.add(x)
return FalseFAQ
Is O(1) always faster than O(n)?
Not for any particular input — O(1) means the cost doesn't grow, not that it's small. A constant 5,000-step operation is O(1); a 10-step loop over a 10-item list is O(n). Big-O compares how they scale: at some input size the O(n) one always falls behind, and that crossover is what the notation captures.
Why is the base of the logarithm never written in O(log n)?
Because log₂ n and log₁₀ n differ only by a constant multiplier (about 3.3×), and constants are dropped. Whether the algorithm halves or tenths the data each step, the shape is the same: O(log n).
What does amortised complexity mean?
An operation that is expensive occasionally but cheap on average across many calls. A Python list append is usually O(1), rarely O(n) when the list resizes — but the resizes are so rare that the average per append stays O(1). You will meet this properly (with the doubling trick that makes it work) in lesson 2.
Do interviewers really reject O(n²) solutions?
Depends on n. For n up to a few thousand, O(n²) passes and stating a working solution first is smart strategy. For n = 10⁵ or more, O(n²) is ~10¹⁰ operations — minutes, not seconds — and the interviewer is waiting for you to improve it. The constraints line tells you which situation you are in.
You can now read the price tag on any piece of code. Next, we meet the first structure and immediately put the skill to work — Lesson 2: Arrays & Strings →