Imagine you write a program that works perfectly on your laptop. It sorts a list of names instantly, finds any student in a database in a blink, and your teacher is impressed. Then someone hands it a list with a million entries instead of a hundred — and suddenly your program takes ten minutes, or an hour, or simply never finishes. Nothing about your code changed. The only thing that grew was the input.
This is the problem Big O notation was invented to describe. It is not a test of how fast your computer is, and it is not really about seconds at all. Big O is a way of answering one simple question: as the input gets bigger, how does the work grow? Once you understand that question, Big O stops being scary math and becomes one of the most practical tools you will ever learn as a programmer. In this guide we will build the idea slowly, with everyday analogies and small pieces of code, until the notation feels natural.
📅 Want a study plan for this topic?
Get a free 7-day learning plan in your calendar — one small lesson every day.
What Is an Algorithm, in Plain Words?
Before we measure algorithms, we need a clear picture of what one is. An algorithm is just a list of steps for solving a problem — nothing more mysterious than a recipe. A recipe for tea says: boil water, add leaves, wait, pour. A recipe for finding a word in a dictionary says: open the middle, decide whether your word comes before or after, repeat with the correct half.
Every program you write is built from such step-by-step recipes. Searching, sorting, recommending videos, finding the shortest route on a map — behind each feature sits an algorithm doing quiet, repetitive work. And here is the key insight: for the same problem, there can be many different recipes, and they are not equally good. One recipe might check every page of the dictionary one by one. Another might halve the book again and again. Both find the word. One of them is dramatically smarter, and Big O is how we express that difference precisely.
What Big O Actually Measures
Big O describes how the resources an algorithm needs grow as the input size grows. The input size is usually written as n — the number of items your algorithm has to deal with: elements in a list, students in a database, pixels in a photo.
Two resources matter most:
- Time complexity — how the number of steps grows as n grows.
- Space complexity — how the extra memory the algorithm needs grows as n grows.
Notice the wording: Big O talks about growth, not exact numbers. It deliberately ignores details like whether your laptop is fast or slow, because those details change from machine to machine, while growth patterns do not. A program that doubles its work every time the input grows by one item will eventually be slow on any computer. Big O also ignores constant factors and small terms: an algorithm that takes 3n + 50 steps is called O(n), because as n becomes huge, the “3” and the “+50” stop mattering compared with the steady march of n itself. Think of it like describing a person’s height as “about six feet” instead of measuring to the millimetre — you keep the part that matters.
The Common Complexities, One by One
Let us meet the growth patterns you will see again and again, from the fastest to the slowest, each with a real-life picture and a tiny example.
O(1) — Constant Time
The work stays the same no matter how big the input is. Real-life analogy: pressing the button for your floor in an elevator. Whether the building has 5 floors or 500, pressing one button is the same single action.
def first_student(students):
return students[0] # one step, alwaysGrabbing the first item of a list, or looking up a value in a dictionary by its key, takes one step whether the list holds ten items or ten million.
O(log n) — Logarithmic Time
Each step cuts the remaining problem in half, so the work grows incredibly slowly. Real-life analogy: finding a word in a paper dictionary. You never read page by page; you open the middle and discard half the book with every flip. Even if the dictionary doubles in size, you need only one extra flip.
def find_page(pages, target):
lo, hi = 0, len(pages) - 1
while lo <= hi:
mid = (lo + hi) // 2
if pages[mid] == target:
return mid
elif pages[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1This is binary search. For a billion sorted items, it needs only about 30 steps. That is the magic of halving.
O(n) — Linear Time
The work grows in direct proportion to the input. Double the input, double the work. Real-life analogy: reading every name on a class attendance sheet to check whether a particular student is present. A sheet of 30 names takes one pass; a sheet of 3,000 names takes a hundred times longer.
def contains(names, target):
for name in names:
if name == target:
return True
return FalseA single loop over n items is the classic O(n) shape. This is often perfectly fine — sometimes you genuinely must look at every item at least once.
O(n log n) — Linearithmic Time
A blend: you do a logarithmic amount of work for each of n items, or split the input repeatedly and process every level fully. Real-life analogy: organising a huge pile of exam papers by repeatedly splitting the pile into smaller sorted piles and merging them back together. It is the pattern behind the fastest general-purpose sorting methods, like merge sort and the sort built into Python.
sorted_scores = sorted(scores) # Python's sort is O(n log n)For large inputs, O(n log n) is dramatically faster than O(n²) below, which is why real-world sorting uses it.
O(n²) — Quadratic Time
The work grows with the square of the input. Double the input, and the work quadruples. Real-life analogy: at a party, every guest shakes hands with every other guest. With 10 guests that is 45 handshakes; with 100 guests it is 4,950; with 1,000 guests, nearly half a million. The usual cause in code is a loop inside a loop:
def print_pairs(students):
for a in students:
for b in students:
print(a, b)For tiny inputs, O(n²) is harmless. For big ones, it is usually the first thing that makes a program crawl.
O(2ⁿ) — Exponential Time
Every extra input item doubles the work. Real-life analogy: a rumour where each person tells two new people, who each tell two more — the crowd explodes. Trying every possible combination, like testing all subsets of items or brute-forcing a password character by character, grows this way. With just 50 items, 2⁵⁰ is over a quadrillion steps. Even small inputs become impossible, which is why exponential algorithms are mostly a warning sign.
A Simple Comparison
Numbers make the difference real. Here is how many steps each pattern needs as n grows:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~33 | 100 | 1,024 |
| 100 | 1 | ~7 | 100 | ~664 | 10,000 | astronomically huge |
| 1,000 | 1 | ~10 | 1,000 | ~9,966 | 1,000,000 | beyond counting |
| 1,000,000 | 1 | ~20 | 1,000,000 | ~20,000,000 | 1,000,000,000,000 | hopeless |
Read the last row slowly. A million items is nothing unusual — a social app passes it before breakfast — yet the gap between O(n log n) and O(n²) is the gap between “instant” and “come back tomorrow.”
How to Analyse a Simple Loop, Step by Step
You do not need advanced math to analyse simple code. Follow three steps: count the work inside the loop, count how many times the loop runs, then multiply and simplify.
total = 0
for score in scores:
total = total + score
print(total)Step one: inside the loop there is one operation (an addition). Step two: the loop runs once per score, so n times. Step three: 1 × n = n, so this is O(n). Now change it slightly:
for a in scores:
for b in scores:
print(a + b)The inner print runs n times for each of the n outer rounds: n × n = n², so O(n²). One more pattern worth memorising: if a loop halves its range each round — like the dictionary search — the loop runs about log n times, giving O(log n). Finally, when a program has separate parts, keep only the biggest growth term: a part that is O(n²) plus a part that is O(n) is simply O(n²), because the larger term eventually swallows the smaller one.
Best Case, Average Case, and Worst Case
The same algorithm can behave differently depending on the input it happens to receive. Searching a list one by one is the classic example. If the item you want is sitting first, you finish in one step — the best case. If it is last, or not there at all, you check everything — the worst case, O(n). Most of the time it is somewhere in the middle — the average case.
When people quote a Big O without saying which case, they almost always mean the worst case. That is not pessimism; it is a promise. The worst case is a guarantee: “no matter what input you give me, it will never be slower than this.” Guarantees are what let engineers build systems that do not collapse on a busy day. As you read about algorithms, train yourself to ask: is this the best, average, or worst case being described?
Common Mistakes Students Make
A few traps catch almost every beginner, so watch for them. First, confusing Big O with exact running time: O(n) does not mean “n seconds,” it means “grows like n.” Two O(n) algorithms can differ in real speed by a constant factor, and that is fine. Second, forgetting that nested loops multiply rather than add — this single misunderstanding causes most wrong answers in exams. Third, ignoring the space side: an algorithm can be fast but hungry, storing a copy of everything it touches. Fourth, assuming the built-in functions are free — sorting inside a loop, for example, quietly adds an O(n log n) cost every round. Finally, many students drop the wrong term when simplifying: in O(n² + n), keep the n², because for large n it dominates completely.
Practice Tips That Actually Work
Start small and stay curious. Take code you have already written — your own loops from class — and analyse it before running it; predict the growth, then test with bigger inputs and watch the time change. Draw the growth curves once by hand; seeing O(n²) bend upward while O(log n) stays nearly flat makes the idea stick far better than definitions do. Learn one pattern at a time and collect real examples of each: one O(1) lookup, one halving search, one nested loop. When you meet a new algorithm, ask the three questions from this guide: What is n? How many times does the main loop run? What dominates? With repetition, analysis becomes a habit rather than a chore, and interview and exam questions start to look like variations on a theme you already know.
Let’s Count It for Real: Finding a Number Two Ways
Big O felt like pure theory to me until I sat down and actually counted the steps on a real list. So let’s do that together — no formulas first, just counting. Here is our list of seven numbers:
nums = [4, 9, 2, 7, 5, 11, 3]Method 1: linear search — check one by one. We are looking for 7. Watch the counter:
| Step | Number checked | Match? | Comparisons so far |
|---|---|---|---|
| 1 | 4 | No | 1 |
| 2 | 9 | No | 2 |
| 3 | 2 | No | 3 |
| 4 | 7 | Yes — found it! | 4 |
Four comparisons to find 7. Now look for 3, the last item: you check all seven numbers — 7 comparisons. And 99, which is not in the list at all? Still 7 comparisons, because you only know it is missing after checking everything. That is why linear search is O(n): the work grows exactly with the size of the list. Double the list, double the worst-case work.
Method 2: binary search — but first, sort. Binary search only works on a sorted list, so sort it: [2, 3, 4, 5, 7, 9, 11]. Now find 7 again, but this time check the middle first:
sorted = [2, 3, 4, 5, 7, 9, 11]
Step 1: middle is 5 (index 3). 7 > 5, so ignore the left half.
Step 2: middle of [7, 9, 11] is 9. 7 < 9, so ignore the right half.
Step 3: only 7 is left. Found it!Three comparisons instead of four — not a huge win on seven items. But here is the part that changed how I think about it: with 1,000 items, linear search needs up to 1,000 checks in the worst case, while binary search needs about 10. With a million items, it is 1,000,000 checks versus about 20. That is the whole point of Big O — it is not about seven items, it is about what happens when the input gets big. In my opinion, if you remember only one pair of numbers from this article, remember 1,000,000 versus 20. That gap is why interviews ask about Big O, and why it matters in real systems.
Try it yourself: take the same list, search for 11 with both methods, and count. Linear search takes 6 comparisons; binary search takes 3. Then imagine the list had a million entries and ask yourself which method you would bet your app on.
Conclusion
Big O notation is simply a language for describing growth. O(1) never grows, O(log n) barely grows, O(n) grows steadily, O(n log n) grows a little faster and powers the world’s sorting, O(n²) grows uncomfortably fast, and O(2ⁿ) explodes. You now know what each pattern means, how to spot it in a loop, why the worst case matters, and how to avoid the mistakes that trip up most beginners. The next time your program feels slow, you will not just have a feeling — you will have a diagnosis. Keep the blog’s motto in mind: Learn, Practice, Build. You have learned the idea today; the practice is yours to enjoy.
Keep learning
📅 Want a study plan for this topic?
Get a free 7-day learning plan in your calendar — one small lesson every day.
Leave a Reply