A ceiling, not a stopwatch
In the previous guide we agreed to stop caring about constants and low-order terms and watch only how a cost scales as the input grows. Big-O is the first notation that turns that agreement into a precise promise. When we write that an algorithm runs in O(n^2), we are saying its cost grows no faster than some fixed multiple of n^2 once the input is large. It is a ceiling on growth, the way 'the drive takes at most three hours' is a ceiling on time — a guarantee about the worst the growth can be, not a claim that it always reaches that worst.
Why a ceiling rather than an exact figure? Because we usually do not know the cost on the nose, and we do not need to. If I promise the drive is at most three hours, you can plan your day even though some trips finish in two. Big-O plays the same role for algorithms: it gives you a worst-case scaling you can rely on across machines and inputs, without forcing you to pin down every detail. That looseness is a feature, but it has a price we will be honest about at the end.
The definition: two witnesses
Here is the precise meaning. We say f(n) is O(g(n)) if there exist a positive constant c and a threshold n0 such that f(n) <= c times g(n) for every n >= n0. The two numbers c and n0 are the witnesses, and producing them is literally what it means to prove a Big-O claim. The constant c answers 'within what factor?' and absorbs the difference between, say, 5n and n. The threshold n0 answers 'starting from what size?' and lets you ignore the messy small-n behavior where low-order terms can dominate.
Watch the two witnesses appear in a tiny proof. Claim: 3n^2 + 5n + 2 is O(n^2). For every n >= 1 we have n <= n^2 and 1 <= n^2, so 5n <= 5n^2 and 2 <= 2n^2, and therefore 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2 = 10n^2. We just exhibited c = 10 and n0 = 1, and the inequality holds forever after. The whole move was to replace each smaller term by a multiple of n^2 — the standard trick in proving an asymptotic bound.
The algebra of bounds
You rarely re-prove bounds from scratch, because a few sum and product rules do the heavy lifting. The sum rule: a sum of finitely many terms is Big-O of its largest term, so O(n^2) + O(n) + O(1) collapses to O(n^2). This is why low-order terms vanish — they are swallowed by the dominant one. The constant rule: a constant times a function does not change its order, so O(100n) is just O(n). Together these say that to read off a Big-O, you find the biggest term and drop everything else.
The product rule covers nesting. If one piece of work costs O(f) and, for each unit of it, you do O(g) more, the total is O(f times g). This is exactly what happens when one loop sits inside another. Multiplication of bounds is the algebra behind nested loops, just as addition is the algebra behind doing one phase after another. With these two operations you can compute the Big-O of most everyday code by inspection, without ever writing down a single c or n0.
The growth zoo, ranked
To use Big-O you need a feel for which function is 'biggest'. The growth-rate hierarchy ranks the common cost functions from gentlest to most violent: constant O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), quadratic O(n^2), cubic O(n^3), higher polynomials O(n^k), exponential O(2^n), and the monstrous factorial O(n!). Each one is dwarfed by the next as n grows, so when the sum rule asks for the largest term, this ladder tells you which it is.
Feel the gaps with n = 1000: log n is about 10, n is 1000, n log n is about 10000, n^2 is a million, while 2^n already has about three hundred digits. The single most consequential boundary on the ladder is between polynomial and exponential: every polynomial, however high its degree, is eventually crushed by any exponential. That polynomial-versus-exponential gap is the dividing line computer scientists draw between 'efficiently solvable' and merely 'not known to be'.
Reading Big-O off loops
The most common place you actually apply all this is a loop. The rule for counting loop iterations is simple: the cost of a loop is the number of times its body runs, times the cost of one pass through the body. A single loop that runs n times with a constant-cost body is O(n). A loop that halves the remaining work each step — like the inner workings of binary search — runs only about log2(n) times, so it is O(log n). The arithmetic of the counter is what sets the count.
Nested loops multiply, by the product rule. The subtlety in nested loop analysis is that the inner loop's count can depend on the outer index. Consider the triangular pattern below: the inner body runs i times when the outer index is i, so the total is 1 + 2 + ... + n. That sum equals n(n+1)/2, which is (1/2)n^2 + (1/2)n. By the sum and constant rules the (1/2)n term and the (1/2) factor both drop, leaving O(n^2). A common slip is to multiply n by n and call it n^2 'because there are two loops' — here the honest count is the triangular sum, which happens to land at the same order, but you should reach it by counting, not by reflex.
for i = 1 to n: # outer runs n times
for j = 1 to i: # inner runs i times when outer = i
do one O(1) step
# total body runs = 1 + 2 + ... + n = n(n+1)/2 -> O(n^2)What Big-O does not tell you
Big-O is powerful precisely because it hides constants and low-order terms — but that same hiding is its main pitfall. Two algorithms can both be O(n log n) while one is ten times slower in practice; the notation cannot see the constant. Worse, an O(n log n) method can lose to an O(n^2) method for small inputs, because the dropped constant in the 'better' algorithm may be large. This is why fast sorts like merge sort often switch to a simple insertion sort once a subarray gets small: at small n, the constants win.
Two more honesties to carry forward. First, Big-O usually describes the worst case over inputs of size n; the average case depends on an assumed input distribution, and a single algorithm can have very different worst-case and average-case bounds. Second, an upper bound is not a verdict at every size — it tells you who wins eventually, not who wins at n = 5. Big-O answers exactly one question: how fast can the cost grow at most? For the matching question 'how fast must it grow at least?' we turn next to Omega and Theta.