What is Big O Notation? A Plain English Guide
Big O notation describes how your code's performance scales as input grows. It's not about exact speed—it's about growth patterns.
The Core Idea
Imagine you're searching for a name in a phone book:
- O(1) - Constant: You know the exact page number. Input size doesn't matter.
- O(log n) - Logarithmic: You use binary search, halving pages each time.
- O(n) - Linear: You scan every page from start to finish.
- O(n²) - Quadratic: For each page, you scan every other page.
Real Code Examples
O(1) - Constant Time
function getFirst(array) {
return array[0]; // Always one operation
}
O(n) - Linear Time
function findItem(array, target) {
for (let item of array) {
if (item === target) return item;
}
return null;
}
Worst case: check every element.
O(n²) - Quadratic Time
function findDuplicates(array) {
const duplicates = [];
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
if (array[i] === array[j]) {
duplicates.push(array[i]);
}
}
}
return duplicates;
}
Nested loops = n × n operations.
Why It Matters
With 1,000 items:
- O(1): 1 operation
- O(log n): ~10 operations
- O(n): 1,000 operations
- O(n²): 1,000,000 operations
That O(n²) function taking 1ms with 100 items takes 100ms with 1,000 items, and 10 seconds with 10,000.
Quick Reference
| Notation | Name | Example |
|----------|------|---------|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single loop |
| O(n log n) | Linearithmic | Good sorting (mergesort) |
| O(n²) | Quadratic | Nested loops |
| O(2ⁿ) | Exponential | Recursive fibonacci |
The Practical Takeaway
Don't prematurely optimize, but recognize these patterns:
- Nested loops over the same data? Probably O(n²).
- Halving data each step? Probably O(log n).
- Single pass through data? Probably O(n).
When your code is slow, Big O helps you understand why—and what to fix.