🎯 By the end of this lesson you can…
- Explain what Big O measures
- Recognise the common complexity classes
- Find the Big O of simple loops
How does the work grow?
| Big O | Name | Everyday example | Rough steps |
|---|---|---|---|
| O(1) | constant | look up a locker by its number | 1 |
| O(log n) | logarithmic | find a word in a dictionary | 20 |
| O(n) | linear | read every page of a book | 1,000,000 |
| O(n log n) | linearithmic | sort a pile of exam papers well | 20,000,000 |
| O(n²) | quadratic | compare every student with every other | 1,000,000,000,000 |
| O(2ⁿ) | exponential | try every combination of a lock | way too many |
Counting the work in code
⚡ JavaScript
big-o-examples.js
👆 Tap a line to explain it
1function first(items) {2 return items[0];3}4function total(items) {5 let sum = 0;6 for (const x of items) sum += x;7 return sum;8}9function hasDuplicate(items) {10 for (let i = 0; i < items.length; i++) {11 for (let j = i + 1; j < items.length; j++) {12 if (items[i] === items[j]) return true;13 }14 }15 return false;16}17console.log(first([7, 8]), total([1, 2, 3]), hasDuplicate([3, 1, 3]));Watch it grow
🐍 Python
growth.py
1import math2print(f"{'n':>8} {'log n':>6} {'n log n':>10} {'n^2':>14}")3for n in [10, 100, 1000, 10000]:4 print(f"{n:>8} {round(math.log2(n)):>6} {round(n * math.log2(n)):>10} {n * n:>14}")Three simplification rules
- Drop constants: O(3n) → O(n). We care about the shape of growth.
- Keep the biggest term: O(n² + n) → O(n²). For big n, n² dominates.
- Different inputs, different letters: looping over list
athen listbis O(a + b), not O(n).
💡 Concept check
A loop runs
n times and inside it another loop runs n times. What is the Big O?💡 Concept check
What is O(5n + 100) simplified?
💡 Concept check
Binary search halves the list at each step. What is its complexity?
🛠️ Count the steps
Write pairs(n) that returns how many handshakes happen when n people each shake hands once with every other person — by actually counting with two nested loops. (Notice how fast the number grows!)
📌 Key takeaways
- Big O describes how work grows as input grows — not exact seconds.
- Drop constants and small terms: O(2n + 5) is O(n).
- One loop over n items → O(n). A loop inside a loop → O(n²). Halving each step → O(log n).
Finished reading & practising?
Saved in this browser. Create a free account to keep it forever.
