Foundations: measuring code · Lesson 1 of 23
Big-O: how code grows
Comparing two solutions without running them: O(1), O(n), O(n²) and O(log n).
Two solutions give the same answer. Which is better? Not "the one that finished first on my laptop": your machine isn't the user's, and today's small input may be a million items tomorrow.
The right question: as the input size (call it `n`) grows, how does the number of steps grow? That's what Big-O measures.
// Three ways to work with an array of n numbers
function first(nums) { // O(1): one step, whatever n is
return nums[0]
}
function total(nums) { // O(n): one step per element
let sum = 0
for (const x of nums) sum += x
return sum
}
function countPairs(nums) { // O(n²): every element against every other
let pairs = 0
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++) pairs++
return pairs
}
const nums = [4, 8, 15, 16, 23, 42]
console.log(first(nums), total(nums), countPairs(nums))| Complexity | n = 10 | n = 1,000 | n = 1,000,000 | Example |
|---|---|---|---|---|
O(1) | 1 | 1 | 1 |
|
O(log n) | ~3 | ~10 | ~20 | Binary search |
O(n) | 10 | 1,000 | 1,000,000 | One loop over the array |
O(n log n) | ~33 | ~10,000 | ~20,000,000 | Good sorting |
O(n²) | 100 | 1,000,000 | 10¹² | A loop inside a loop |
At a million items, O(n log n) versus O(n²) is the difference between a second and weeks.
Three rules that simplify counting
1. Drop constants: 2n and n + 100 are both O(n). We care about the shape, not the exact count.
2. Keep the biggest term: n² + n is O(n²); as n grows, n² swallows the rest.
3. Loops in sequence add, nested loops multiply: two separate loops = O(n + n) = O(n). A loop inside a loop = O(n × n) = O(n²).
- ▶let steps = 0
- 2let n = 16
- 3while (n > 1) {
- 4 n = Math.floor(n / 2)
- 5 steps++
- 6}
- 7console.log(steps)
Variables
| steps | 0 |
Output
Why is log n so small? Each step halves the problem.
Quick question
What's the complexity of this code?
for (const a of nums) { if (nums.includes(a * 2)) count++ }
What's the output?
let count = 0 for (let i = 0; i < 4; i++) for (let j = 0; j < 4; j++) count++ for (let k = 0; k < 4; k++) count++ console.log(count)
What will this code print?
Exercise
Write hasDuplicate(nums) in O(n) (no loop inside a loop). The program must print true false.
Expected output: true false
function hasDuplicate(nums) {
}
console.log(hasDuplicate([3, 1, 4, 1]), hasDuplicate([2, 7, 1, 8]))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 3 games
Sign in to save your progress and earn XP.