What Is Big O Notation?
Big O notation is the standard language developers use to describe how an algorithm's performance scales as the size of its input grows. It doesn't measure raw speed — it measures growth rate. Understanding it is essential for writing efficient code and acing technical interviews.
Why Big O Matters
Imagine you have two functions that both sort a list. On 10 items, both finish instantly. But on 1,000,000 items, one takes a second and the other takes days. Big O notation helps you predict that difference before you run the code.
The Most Common Complexities
Here's a quick reference from fastest to slowest growth:
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Iterating through a list once |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Bubble sort, nested loops |
| O(2ⁿ) | Exponential | Recursive Fibonacci (naïve) |
Breaking Down Each Class
O(1) — Constant Time
No matter how large the input, the operation takes the same amount of time. Reading the first element of an array is always one step, whether the array has 5 or 5 million items.
O(log n) — Logarithmic Time
Each step eliminates a large portion of the remaining work. Binary search is the classic example: you halve the search space with every comparison. An input of 1,000,000 elements requires only about 20 comparisons.
O(n) — Linear Time
Work grows proportionally with input size. A single loop through an array of n items is O(n). Doubling the input doubles the time.
O(n²) — Quadratic Time
Common with nested loops. If you compare every element against every other element, you get n × n operations. This becomes painfully slow at scale — 10,000 items means 100,000,000 operations.
How to Analyze Your Own Code
- Identify loops: A single loop = O(n). Nested loops = O(n²) or worse.
- Identify recursive calls: Count how many times the function calls itself and with what input size.
- Drop constants and lower-order terms: O(2n + 5) simplifies to O(n). We care about shape, not the exact formula.
- Consider the worst case: Big O typically describes the worst-case scenario unless stated otherwise.
Space Complexity Too
Big O applies to memory usage, not just time. An algorithm that creates a new array proportional to input size uses O(n) space. An in-place sort uses O(1) space. Always consider both dimensions when evaluating an algorithm.
Practical Takeaway
You don't need to obsess over micro-optimizations, but you should always be able to reason about your code's complexity class. Choosing an O(n log n) sort over an O(n²) sort is one of the highest-leverage decisions you can make as a developer. Big O gives you the vocabulary to make that call with confidence.