Big-O notation
How the cost grows as the input grows. Not how long anything takes.
Big-O describes how the work grows as the input grows. It says nothing about how fast the code runs on your machine, and that is deliberate — it is a property of the algorithm, not of the hardware.
The common rates
| Notation | Name | Example |
|---|---|---|
| O(1) | constant | list.get(i), map.get(key) |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning an array once |
| O(n log n) | linearithmic | any good general-purpose sort |
| O(n²) | quadratic | nested loop over the same data |
| O(2ⁿ) | exponential | naive recursive subset generation |
The gaps between these are enormous and the intuition is worth building. At a million elements: O(log n) is about twenty steps, O(n) is a million, O(n log n) is twenty million, and O(n²) is a trillion — the difference between instant and never.
Reading it off code
One loop over the input is O(n):
for (int i = 0; i < n; i++) { ... }
A loop inside a loop, both over the input, is O(n²):
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) { ... }
Halving the problem each pass is O(log n):
while (n > 1) { n = n / 2; }
Sequential blocks add and the larger wins: an O(n) loop followed by an O(n²) loop is O(n²). Nested loops multiply.
What it ignores
Constants. O(n) and O(100n) are both O(n). For a specific n the constant may dominate completely, which is why an O(n log n) sort can lose to insertion sort on twenty elements — and why the library switches to insertion sort for small ranges.
Lower-order terms. n² + n is O(n²).
The best case. Plain O() is normally the worst case unless stated. Quicksort is O(n log n) typically and O(n²) in the worst case, which is why the library uses a variant chosen to make that worst case hard to trigger.
The practical use
You are not going to calculate this often. What it is for is noticing the accidental quadratic — the contains inside a loop, the string concatenation in a loop, the repeated indexOf. Those work fine on ten items in testing and fall over on ten thousand in production, and they are the single most common performance bug in ordinary code.