Big O Notation
Task: Watch how each complexity class grows as the input gets bigger
Why we need Big O
Analogy
Imagine different roads to the same city:
- O(1): A private jet - always the same time, no matter distance.
- O(n): A straight highway - time grows with distance.
- O(n²): A winding mountain path - time grows much faster.
Big O tells us which "road" (algorithm) scales better as the journey (input size) gets longer.
What is Big O?
Definition
Big O notation measures how fast an algorithm grows as input size increases.
It focuses on the worst-case scenario.
Example: Searching through a list one by one is O(n) because time grows linearly with input size.
Why use Big O?
- Helps compare algorithms without running them.
- Ignores constants and small terms - only the dominant growth factor matters.
- Example:
O(3n + 5)simplifies toO(n).
Common complexities
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array index lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Loop through an array |
| O(n log n) | Linearithmic | Merge sort |
| O(n2) | Quadratic | Nested loops |
| O(2n) | Exponential | Generating every subset |
| O(n!) | Factorial | Trying every possible ordering |
How to find Big O
Count operations relative to input size
Drop constants
e.g.
3n → nKeep the highest-order term
e.g.
n² + n → n²
Result: O(n2) is the Big O complexity.
Why should you care about Big O?
Because an algorithm that works perfectly with 100 items might become painfully slow with 10 million items.
Big O helps you compare algorithms before you run them. For example:
| Complexity | Verdict |
|---|---|
| O(1) | 🚀 Excellent |
| O(log n) | 🚀 Very good |
| O(n) | 👍 Usually good |
| O(n log n) | 👍 Often good |
| O(n2) | ⚠️ Can become expensive |
| O(2n) | 🚨 Explodes very quickly |
Key takeaway
Big O is about understanding how an algorithm scales as the input grows.