← Big-O · guided lesson
Big-O & Complexity
the story
Big-O notation (with Ω and Θ)
Every tool here exists because something was too slow or broke without it. Here is what.
Big-O came from number theory, not computing. Paul Bachmann used O in his 1894 book on analytic number theory; Edmund Landau spread it through his 1909 handbook on primes, and added little-o. In 1976 Donald Knuth saw people using O for lower bounds, where it doesn't fit. In "Big Omicron and big Omega and big Theta" (SIGACT News) he proposed Ω for "order at least" and Θ for "order exactly" — the notation algorithm analysis uses today.
the problem it solved
Comparing algorithms without depending on the computer, the language or the compiler — only on how the work grows.
why it matters: without it
You'd only learn an algorithm is too slow after running it on real data — usually in production, on the biggest input.
sources: Knuth — Big Omicron and big Omega and big Theta (SIGACT News, 1976) ↗
also in this chapter: Time complexity & the input-size budget · Amortized analysis
the idea
The idea in 30 seconds
Big-O describes how the number of steps grows as the input gets bigger — ignoring constants and small terms.
One loop over n items → O(n). A loop inside a loop → O(n²). Halving each step → O(log n).
Space complexity is the same idea for memory: extra arrays, maps, and the recursion stack all count.
picture this
Finding "Priya" in 2,000 phone contacts: scrolling from the top checks up to 2,000 names — O(n). Jumping to the middle of the sorted list and halving each time needs about 11 checks — O(log n). Hunting duplicate contacts by comparing every pair needs about 20 lakh checks — O(n²).
watch it
Growth race
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Growth race
Grow n one step at a time. To scale, the exponential bar makes everything else look flat.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Which complexity fits which n? (3D)
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Which complexity fits which n? (3D)
Height = digits in the step count. The green staircase is the input-size table every competitive programmer memorises.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Count the dominant work, drop constants: 3n + 5 → O(n); n² + 100n → O(n²). Big-O is about the shape of growth, not exact time.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Loop shapes: sequential loops add (O(n + m)); nested loops multiply (O(n·m)); a loop that halves or doubles is O(log n).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
log n is tiny: log₂ of a million is ~20, of a billion ~30. It counts how many times you can halve n before reaching 1.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Best / average / worst: quote the worst case unless you say otherwise. HashMap is O(1) average; quicksort is O(n log n) average but O(n²) worst.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Amortized O(1): an operation that is occasionally expensive but cheap on average over a long sequence — ArrayList add copies on growth, yet n adds cost O(n) total.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Space counts the recursion stack: recursing n levels deep uses O(n) memory even with no arrays. Halving recursion uses O(log n).
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Constraints → target complexity: n ≤ 10 → n!, ≤ 20 → 2ⁿ, ≤ 500 → n³, ≤ ~5,000 → n² (10⁴ is borderline), ≤ 10⁶ → n log n, ≤ 10⁸ → n (assuming ~10⁸ simple steps per second).
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Library calls aren't free: list.contains, list.remove(0), substring and += on strings are all O(n) — inside a loop they make O(n²).
spot the pattern
When you see this, think this
A loop variable that halves or doubles (
i /= 2,i *= 2,lo..hishrinking by half)O(log n)
A loop nested inside another loop over the same input
O(n²) — unless the inner pointer never resets (then it's O(n) total)
Two pointers or a sliding window where each pointer only moves forward
O(n) amortized: each index is visited a constant number of times
Sorting before the main loop
At least O(n log n)
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Calling a nested loop O(n²) when the inner loop's pointer never resets — two pointers / sliding window are O(n).
- Forgetting library costs:
contains,indexOf,remove(0),substring,+=on strings are O(n).
quick check
One question. No pressure.
What is the time complexity of for (int i = 1; i < n; i *= 2) { ... O(1) ... }?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Sqrt(x)
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why is 3n + 5 written as O(n)?
Question 1: Why is 3n + 5 written as O(n)?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.