Big O Notation
Reference for Big O — O(1), O(log n), O(n), O(n log n), O(n²).
Compares how sorting, searching, and graph algorithms scale with growth rate examples.
The Formula
O(f(n)) — describes the upper bound of growth rate as n → ∞
Big O notation expresses how an algorithm's runtime or space usage scales with input size. It focuses on the dominant term and ignores constants and lower-order terms.
Variables
| Symbol | Meaning |
|---|---|
| n | Size of the input |
| O(1) | Constant time — does not depend on input size |
| O(log n) | Logarithmic time — halves the problem each step (e.g., binary search) |
| O(n) | Linear time — examines each element once |
| O(n log n) | Linearithmic time — efficient sorting algorithms |
| O(n²) | Quadratic time — nested loops over the input |
| O(2ⁿ) | Exponential time — doubles with each additional input element |
Example 1
Comparing O(n) vs O(n²) for n = 1,000
O(n): approximately 1,000 operations
O(n²): approximately 1,000,000 operations
The quadratic algorithm does 1,000 times more work
Example 2
Binary search on a sorted array of 1,000,000 elements
Complexity: O(log n)
log₂(1,000,000) ≈ 20
At most about 20 comparisons to find any element
When to Use It
Use Big O notation when:
- Comparing the efficiency of different algorithms
- Predicting how an algorithm will perform on larger inputs
- Choosing the right data structure for a problem
- Identifying performance bottlenecks in code
Key Notes
- Big O is an upper bound (worst-case) — O(n²) means no more than cn² steps for large n; Ω (omega) is the lower bound, and Θ (theta) is the tight bound; most informal comparisons use Big O to mean the dominant term in average case as well
- Constants and lower-order terms are dropped: O(3n² + 7n + 5) simplifies to O(n²) — valid for large n but can mislead for small inputs where constants dominate; a well-cached O(n²) algorithm can outperform a poorly-cached O(n log n) one for n < 1,000
- Space complexity also uses Big O — a recursive algorithm that calls itself n times uses O(n) stack space even if each call is O(1); ignoring space complexity causes stack overflows in production when input size exceeds expectations
- O(2ⁿ) and O(n!) are practically intractable: n = 30 already means over a billion operations for O(2ⁿ) — problems in these classes signal the need for dynamic programming, greedy algorithms, or approximation methods