Big O notation describes how the work an algorithm does grows as its input grows. It won't tell you how many milliseconds your code takes, but it tells you whether doubling the data barely changes the wait, doubles it or makes it four times longer, and that is usually what decides whether code copes with real data.
What Big O measures
Big O counts steps as a function of n, the size of the input: the number of items in a list, characters in a string or rows in a table. You write it as O(...) and read it as 'order of'. O(n) means the work grows in proportion to n.
It describes the shape of the growth, not an exact count, so two simplifications always apply:
- Drop the constants. A function that does
3n + 5steps isO(n). The 3 and the 5 depend on the language and the machine; the growth doesn't. - Keep only the biggest term.
n² + nisO(n²). Once n is large, the n² part dwarfs everything else.
Unless someone says otherwise, a Big O figure describes the worst case: the input that makes the algorithm work hardest. That is the case you have to plan for, because it is the one that turns up in production.
O(1): constant time
An O(1) operation takes the same number of steps however big the input is. Reading the first item of a list is the classic example:
Wondering how this was made? How we make these