Big O Notation Reference
Understand Big O notation for algorithm complexity.
Covers O(1), O(log n), O(n), O(n log n), O(n2), and O(2n) with examples.
What is Big O?
Big O notation describes the worst-case performance of an algorithm. It tells you how the running time or memory usage grows as the input gets larger.
Common Complexities (Fastest to Slowest)
| Big O | Name | Example |
|---|---|---|
| O(1) | Constant | Array index lookup, hash table access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Scanning through a list |
| O(n log n) | Linearithmic | Merge sort, quick sort (average) |
| O(n²) | Quadratic | Bubble sort, nested loops |
| O(n³) | Cubic | Matrix multiplication (naive) |
| O(2ⁿ) | Exponential | Recursive Fibonacci, power set |
| O(n!) | Factorial | Traveling salesman (brute force) |
Growth Comparison
| n | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 7 | 100 | 664 | 10,000 | 1.27 × 10³⁰ |
| 1,000 | 10 | 1,000 | 9,966 | 1,000,000 | Huge |
| 10,000 | 13 | 10,000 | 132,877 | 100,000,000 | Huge |
Example 1
What is the time complexity of searching for a value in a sorted array using binary search?
Binary search halves the search space each step
After k steps, the remaining space is n / 2ᵏ
It stops when n / 2ᵏ = 1, so k = log₂(n)
Time complexity: O(log n)
Example 2
What is the time complexity of checking all pairs in an array of n elements?
The outer loop runs n times
The inner loop runs up to n times for each outer iteration
Total operations: n × n = n²
Time complexity: O(n²)
When to Use It
Use Big O notation to evaluate and compare algorithms:
- Choosing the right data structure for a given problem
- Predicting performance as data grows from hundreds to millions of records
- Identifying bottlenecks in code during optimization
- Communicating algorithmic efficiency in technical discussions