Academy
Foundations of Computing

Lesson 10 of 10

Big-O Notation

"Premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." — Donald Knuth

Every program you have ever written was fast — on your machine, with your test data. Big-O is the language engineers use to answer a harder, more honest question: what happens when the data gets big? It is the single most reliable predictor of whether code that works in a demo will still work when a million people show up — and, not coincidentally, the concept interviewers reach for first.

The question this chapter answers

Your code runs instantly on 100 users. Will it still be standing at 100 million — or will it quietly fall over, and could you have known in advance?

Core Concepts

Big-O describes how the work an algorithm does grows as its input grows. Notice what it is not: it is not seconds, not milliseconds, not "fast" or "slow." A stopwatch measures your laptop on a good day. Big-O measures the shape of the growth — and shape is what betrays you at scale. We write it as O(f(n)), where n is the size of the input and f(n) is roughly how many steps you take.

Two rules turn a messy step-count into a clean Big-O, and they are the two moves interviewers watch for:

  • Drop the constants. O(2n) and O(n) are the same class — doubling the work doesn't change the shape of the curve. So we say O(n).
  • Keep only the dominant term. O(n² + n) becomes O(n²) — as n grows, the n² swamps everything else.

That leaves a small family of curves you must know cold. Here is what each one actually costs — the last two columns are why this matters:

Big-O Name Example n = 10 n = 1,000,000
O(1) Constant Look up a key in a hash map 1 1
O(log n) Logarithmic Binary search a sorted array 3 20
O(n) Linear Scan a list once 10 1,000,000
O(n log n) Linearithmic A good sort (merge / quick) 33 ~20 million
O(n²) Quadratic Compare every pair (nested loop) 100 1,000,000,000,000
O(2ⁿ) Exponential Try every subset 1,024 a 301,030-digit number

Read the last column again. At a million items, an O(n) scan is a million steps — a blink. The O(n²) version is a trillion. Same input, same correct answer, and one of them never finishes. That gap is the whole subject.

Seeing it in code

The most common real example — "does this list contain a duplicate?" — written twice. Same output, different shape. Run it, then change the list and run it again:

Python — Try it Yourself
Loading editor…
Output
Click Run to execute the code.

The fast version trades a little space (the set) for a lot of time. That trade — memory for speed — is one of the most important instincts in engineering, and Big-O is how you reason about both sides of it. (Yes: there's also space complexity, measured the same way. The slow version is O(1) space; the fast one is O(n) space.)

One more distinction interviewers love: best, average, and worst case. has_dupe_fast might return on the second item (best case, O(1)) or scan everything (worst case, O(n)). When we say an algorithm "is O(n)" with no qualifier, we almost always mean the worst case — because worst case is what wakes you at 3am.

Everyday analogy

Finding "Okoro" in a phone book. Reading name by name from page one is O(n) — a million names, up to a million glances. Opening to the middle, deciding "before or after," and repeating is O(log n) — a million names in about 20 glances. Same book, same goal. One approach scales to a city; the other doesn't. Binary search only works because the book is sorted — which is why sorting (an O(n log n) cost, paid once) unlocks fast lookups forever after.

History changed here

The notation isn't from computer science at all. The German mathematicians Paul Bachmann and Edmund Landau used "big O" in the 1890s to describe how number-theory functions grow. It sat in pure maths for seventy years until Donald Knuth, writing The Art of Computer Programming in the 1960s, borrowed it for algorithms — arguing the field needed a shared, machine-independent way to compare them. That last idea is the gift: Big-O lets you reason about an algorithm without knowing the language, the CPU, or the year. It has outlived every computer it was ever run on.

The engineer's notebook

What experienced engineers actually do with this, day to day:

• They spot the nested loop. Two loops over the same data is the O(n²) smell — the first thing to check when something "gets slow as we grow."
• They reach for a hash map to buy O(1). "Can I remember this instead of re-searching for it?" turns a lot of O(n²) into O(n).
• They know constants still matter in the real world. Big-O ignores them, but an O(n) pass that hits the database on every item can be slower than an O(n log n) one that stays in memory. Big-O tells you the shape; profiling tells you the reality. Pros use both.

Real-world example — chika.ng Academy

The Academy verifies a certificate at /verify/<code>. Naively, you could scan every quiz attempt in the database and compare — O(n) in the number of attempts, getting slower with every student who ever passed. Instead the code is a lookup by primary key: the database's index makes it effectively O(log n), near-instant whether there are 100 certificates or 100 million. Indexes are just sorted phone books your database keeps for you — which is the entire reason the "Indexes" chapter exists later in this Volume.

Common Mistakes

  • Confusing Big-O with speed. "O(1) is always faster than O(n)" is false for small n with big constants. Big-O is about growth, not a stopwatch.
  • Keeping constants and lower terms. Saying "O(2n + 5)" in an interview signals you haven't internalised the rules. It's O(n).
  • Counting only loops. A single line like x in a_list is a hidden O(n) scan. Put it inside a loop and you've built O(n²) without writing a nested loop.
  • Forgetting space. Your O(n)-time fix might quietly use O(n) memory. At scale, memory runs out too.
  • Optimising the wrong thing. Turning an O(n) step that runs once into O(log n) while an O(n²) monster sits next to it. Find the dominant term first.
Thought experiment

An O(n²) algorithm handles n = 1,000 in exactly 1 second. Your product succeeds and n grows to 1,000,000 — a thousand times more data. How long does one run take now? Not a thousand seconds. The work grows with the square, so it's a million times more: about 11.6 days. The same success that grew your data by 1,000× grew your runtime by 1,000,000×. That is the moment a startup's "it was fine last month" becomes an outage — and the moment you'll be glad you can see it coming.

Interview Corner

Interview Corner — the same idea at three levels. Answer yours; recognise the one above it.
Junior
"What's the time complexity of this function, and why?" (a single loop over the input)
Model answer — "It's O(n). There's one loop that visits each of the n items once, and the work inside is constant, so the total grows in direct proportion to the input."
Follow-up they'll throw: "And if I nest a second loop over the same list inside it?" → O(n²). Say why: for each of n items you now do n units of work.
Intermediate
"Why is O(n log n) the practical limit for comparison sorting, and when would you accept O(n²)?"
Model answer — "Any sort that works by comparing pairs can't beat O(n log n) — that's a proven lower bound. I'd still accept an O(n²) sort like insertion sort for small or nearly-sorted inputs, where its low constant factor and simplicity win. Big-O describes the limit; the real choice depends on n and the data's shape."
Follow-up: "Could you sort faster than n log n?" → Yes, non-comparison sorts (counting / radix) hit O(n) for bounded integer keys. Knowing the exception is a senior signal.
Senior
"A page listing a user's mutual connections is timing out as the platform grows. Diagnose and fix it, in Big-O terms."
Model answer — "First I'd find the dominant term. 'Mutual connections' smells like comparing one user's friends against another's — if that's a nested scan it's O(a × b), roughly O(n²), which explains timeouts at scale. The fix trades space for time: put one user's friends in a hash set (O(a)), then scan the other once checking membership in O(1) each — total O(a + b), linear. If it's still hot, move the work off the request path — precompute and cache — because the fastest O(n) is the one you don't run live."
This is a system-design answer wearing a complexity costume. That's the senior move: name the complexity, then reach past the algorithm to caching and precomputation.
Company lens — how the same topic gets asked
micro1Live and conversational. The AI interviewer wants to hear you reason out loud — state the complexity, then justify it. Silence reads worse than a wrong first guess you correct.
GoogleWants the exact class and the trade-off. Expect "can you do better?" until you hit the optimum — be ready to prove the lower bound.
MicrosoftValues clean, structured reasoning over cleverness. Narrate the two rules as you apply them.
Amazon / AWSOperational lens: "what happens at 100× traffic, and what does it cost?" Tie complexity to scale, memory and dollars — not just steps.
Hands-on exercise
  1. State the Big-O of a function that, for every product in a list, loops through an orders list to count sales. Then rewrite it to be linear using a dictionary of counts — and state the new time and space complexity.
  2. In the editor above, run has_dupe_slow and has_dupe_fast on a list of 5,000 numbers and compare. Predict which is faster before you run it.
  3. Out loud (as in a micro1 screen), explain in one breath why doubling the input roughly quadruples an O(n²) algorithm's work.

Chapter Summary

  • Big-O measures how work grows with input size — the shape of the curve, not a stopwatch reading.
  • Simplify by dropping constants and keeping the dominant term: O(2n² + n) → O(n²).
  • Know the family cold: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
  • Hash maps buy O(1) lookups; the classic fix is trading space for time to turn O(n²) into O(n).
  • "An algorithm is O(n)" usually means worst case. Mind space complexity too.
  • Big-O predicts the cliff before you drive off it — which is why interviews start here.
Narrative bridge

We now have a language for how algorithms scale. But an algorithm is only as good as the data it runs on — and how you arrange that data decides which complexities are even possible. That's where we turn next: Part II, and the humble building block everything rests on — the Variable.

Editorial reflection — most engineers meet Big-O as a hoop to jump through for interviews, then forget it. That's backwards. The interview asks about it because it's the closest thing our field has to foresight: a way to know, before you ship, whether success will be the thing that breaks you. Learn it as a superpower, and the interview takes care of itself.

Enrol to track progress

Q&A · 0

Enrol to ask questions and join the discussion.

No questions yet — be the first to ask.