Why we throw away the details
In the last guide we learned to write running time as a function of the input size n, and to take the worst case over all inputs of that size. So we might end up with something like "this sort takes 3n^2 + 5n + 17 comparisons in the worst case." That is honest, but it is also fragile: change the machine, count assignments instead of comparisons, or tweak the inner loop, and every one of those numbers shifts. The 3, the 5, and the 17 are accidents of bookkeeping; the n^2 is the real story.
The fix is to deliberately blur our eyes. We agree to ignore constant factors (the 3) and lower-order terms (the 5n and the 17), and to care only about how the cost behaves as n grows large. This is asymptotic analysis: the behaviour "in the limit," once n is big enough that one term dwarfs the rest. The reward is a comparison that is stable across machines and survives the small implementation choices that should never have decided which algorithm wins.
Three relatives: O, Omega, and Theta
Big-O is the one everyone quotes, and it captures an UPPER bound on growth. Saying an algorithm runs in O(n^2) means: there is some constant c and some threshold n0 such that, for every input size n at least n0, the running time is at most c * n^2. In words, "it grows no faster than n^2, once you ignore constants and small cases." It is a ceiling, a promise about how bad things can get — not a claim that it is ever exactly that slow.
Big-O has two relatives that round out the family. Big-Omega (written with the Greek letter Omega) is the mirror image: a LOWER bound, "grows at least this fast." An algorithm that is Omega(n) cannot possibly finish in fewer than c * n steps for large n. Big-Theta (the Greek letter Theta) is the tight sandwich: f is Theta(g) when it is BOTH O(g) and Omega(g), so g pins the growth from above and below at once. Theta is what you really mean when you want to say "this is exactly an n-log-n algorithm, no better and no worse."
The ladder of growth rates
Once we agree to read costs asymptotically, almost every algorithm you will ever meet lands on one of a handful of rungs. The ladder of growth rates lists them from gentlest to most ferocious, and each rung utterly dominates the one below as n grows: a slower-growing function is eventually smaller, no matter how big its constants. Memorising the ORDER of this ladder is worth more than any single proof, because it tells you at a glance whether doubling the input is a yawn or a catastrophe.
rung grows like n=10 n=1000 everyday picture -------- ----------- ---------- -------------- ----------------------------- constant 1 1 1 look up a value by its key log log n ~3 ~10 binary search a sorted list linear n 10 1000 scan a list once linearith n log n ~33 ~10000 a good comparison sort quadratic n^2 100 1000000 compare every pair cubic n^3 1000 10^9 naive matrix multiply poly n^k ... ... still 'tame': one rung's family exp 2^n 1024 ~10^301 try every subset of n items factorial n! ~3.6e6 astronomically try every ordering of n items
The single most important boundary on this ladder is the line between the polynomial rungs (n, n^2, n^3, and so on — any fixed power n^k) and the exponential ones (2^n, n!, and worse). Below the line, growth is polynomial: doubling the input multiplies the cost by a fixed factor, so bigger computers and patience keep pace with bigger problems. Above the line you hit exponential blow-up, where adding ONE more item can double the work. That cliff is the whole reason the next guide singles out polynomial time as the dividing line of feasibility.
Why exponential growth is a wall, not a hill
It is tempting to think exponential algorithms are merely "slow," the way n^3 is slower than n. They are not in the same league. Picture a problem that tries every subset of n items: there are 2^n subsets, so the work doubles with each item added. At n=40 that is about a trillion subsets — a few minutes on a fast machine. At n=60 it is a million times more. At n=100 the count exceeds the number of atoms in the observable universe. No faster chip, no bigger data centre, no clever caching rescues you, because each new item undoes all of last decade's hardware progress in a single step.
This is what theorists mean by intractability: not "we have not found a fast method yet" but "the resources required outrun anything physically buildable as the input grows." A polynomial algorithm with a friendly exponent scales gracefully; an exponential one slams into a wall at a fixed, fairly small input size and never recovers. That qualitative difference — graceful versus catastrophic — is exactly why the field draws its main dividing line where it does.
Reading off a bound: a tiny worked example
Let us turn the loose phrase "ignore constants and small terms" into a recipe you can apply by eye. Suppose we counted the steps of some procedure and got exactly T(n) = 4n^2 + 100n + 9 in the worst case. We want the tightest simple bound — a Theta if we can get it. Here is the routine.
- Find the dominant term — the one that grows fastest as n increases. Among 4n^2, 100n, and 9, the n^2 term wins, because for large n any quadratic eventually buries any linear or constant term.
- Drop the lower-order terms. 100n and 9 are swept into the dust; we are left with 4n^2.
- Drop the constant factor. The 4 is an accident of how we counted, so we discard it and keep n^2.
- State the bound. T(n) is O(n^2) (no worse), Omega(n^2) (no better — the dominant term really is quadratic), and therefore Theta(n^2): a tight, machine-independent verdict.
Notice the threshold from the definition quietly at work: 4n^2 + 100n + 9 is bigger than 4n^2 for every n, so it is NOT bounded above by 4n^2 alone — but it IS bounded above by, say, 5n^2 once n is at least 100 (try it: at n=100 the 100n + 9 finally fits inside the extra n^2). That "once n is big enough" clause is the n0 in the definition, and it is what licenses us to ignore the small-input mess and report a clean Theta(n^2).