MainExamplesHistoryRecommended Reading
Big O notation describes how fast an algorithm is, or how much memory it uses, as the input size grows. It's like rating a car's fuel efficiency — it tells you how performance changes as you drive more miles.
Why It Matters:
Big O helps you understand if your algorithm will scale. An algorithm that's fast with 10 items might be unusable with 10 million items.
Common Complexities:
- O(1): Constant time — instant, regardless of input size
- O(log n): Logarithmic — very fast, like binary search
- O(n): Linear — grows proportionally with input
- O(n log n): Linearithmic — efficient sorting algorithms
- O(n²): Quadratic — nested loops, gets slow fast
- O(2ⁿ): Exponential — very slow, avoid if possible
Examples:
- Looking up in a hash table: O(1) — instant
- Searching an array: O(n) — might check every item
- Nested loops: O(n²) — for each item, check all items
What Big O Doesn't Tell You:
- Exact runtime (just growth rate)
- Best case performance (usually worst case)
- Constants (O(100n) is still O(n))
FAQ
Is O(n) always better than O(n²)?
Usually yes, but for small inputs, the difference might not matter. Big O describes behavior as input grows large.
What's the difference between time and space complexity?
Time complexity is how runtime grows. Space complexity is how memory usage grows. Both use Big O notation.
Do I need to know Big O?
Yes! It's essential for interviews and helps you write efficient code. Understanding it makes you a better programmer.