Big-O Notation
Big-O notation describes the upper bound of an algorithm’s growth rate as input size approaches infinity. It gives us a language to compare algorithm efficiency independent of hardware or implementation details.
Common Complexity Classes
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array access by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, heapsort |
| O(n²) | Quadratic | Bubble sort, selection sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci (naive) |
| O(n!) | Factorial | Traveling salesman (brute force) |
Key Rules
- Drop constants: O(2n) → O(n)
- Drop lower-order terms: O(n² + n) → O(n²)
- Focus on dominant term: O(n² + n log n + n) → O(n²)
Amortized Analysis
Amortized analysis averages the cost of a sequence of operations, showing that expensive operations are rare enough to be absorbed by cheap ones. A classic example is dynamic array resizing — individual appends occasionally cost O(n) for resizing, but the amortized cost is O(1).