Big O Notation
Big O notation is a mathematical framework for describing the upper bound of an algorithm’s time or space complexity as input size grows. It abstracts away constants and lower-order terms to focus on the dominant factor that determines scalability — making it the standard language for comparing algorithm efficiency.
The notation expresses worst-case growth rates: O(1) for constant time, O(log n) for logarithmic, O(n) for linear, O(n log n) for linearithmic, O(n²) for quadratic, and O(2ⁿ) for exponential. Understanding these classes is essential for choosing appropriate sorting algorithms, search strategies, and data structures for a given problem.
Key Concepts
Asymptotic Analysis — Big O describes behavior as n approaches infinity. An O(n²) algorithm may outperform O(n log n) for small inputs due to constant factors, but will always lose at scale.
Common Complexity Classes:
| Class | Name | Example |
|---|---|---|
| O(1) | Constant | Hash table lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Array scan |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Nested loops |
| O(2ⁿ) | Exponential | Brute-force subset enumeration |
Space Complexity — Big O applies to memory usage as well. An algorithm that creates a copy of its input is O(n) space; one that sorts in-place is O(1) auxiliary space.
Amortized Analysis — Some operations are occasionally expensive but cheap on average. Dynamic array appends are O(1) amortized despite occasional O(n) resizing.
Common Pitfalls
- Ignoring constant factors for small inputs — O(n) with a large constant can be slower than O(n²) for n < 100
- Confusing Big O (upper bound) with Big Theta (tight bound) — O(n) technically includes O(1), but Θ(n) means exactly linear
- Overlooking space complexity when optimizing for time
Best Practices
- Always consider both time and space complexity when evaluating algorithms
- Profile with realistic input sizes rather than relying solely on theoretical analysis
- Use amortized analysis for data structures with occasional expensive operations
Related Topics
- recursion — Recursive algorithms often have complexity defined by recurrence relations
- dynamic-programming — Trades space for time to reduce exponential complexity to polynomial