Big O Notation
Big O notation describes the upper bound of an algorithm's growth rate as input size increases.
Common Complexities
| 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 |
| O(n²) | Quadratic | Bubble sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci |
Key Rules
- Drop constants: O(2n) becomes O(n)
- Drop lower-order terms: O(n² + n) becomes O(n²)
- Consider worst case: Unless otherwise stated, Big O refers to worst-case performance
Example: Linear Search
function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// Time: O(n) — we may need to check every element
// Space: O(1) — no extra memory used
Practice
Try analyzing the time complexity of your own code. Count the number of operations relative to the input size.