Why line the animals up at all
By now you can read Big-O as a ceiling and Big-Theta as a tight verdict. But a running time of Theta(n log n) only means something once you have an instinct for where n log n sits — is it close to linear, or close to n^2? The point of this guide is to build that instinct. We are going to take the handful of functions that show up again and again in algorithm analysis and arrange them in a strict pecking order — the growth-rate hierarchy — so that when a Theta lands on one of them you immediately know how the cost scales.
Here is the famous lineup, slowest-growing on the left, written as Theta classes: Theta(1) < Theta(log n) < Theta(sqrt n) < Theta(n) < Theta(n log n) < Theta(n^2) < Theta(n^3) < Theta(2^n) < Theta(n!). The "<" here is the strict-domination relation: each function is eventually overtaken, by any constant factor you like, by the one to its right. That is exactly the little-o relationship from the previous guide — log n = o(sqrt n), n^2 = o(2^n), and so on down the line.
The gentle end: constant, log, and linear
Theta(1), constant time, is the dream: the work does not grow with the input at all. Looking up an array element by index, or pushing onto a stack, costs the same whether n is ten or ten billion. Theta(log n), logarithmic time, is almost as good — it grows, but with breathtaking laziness. The clean way to feel a logarithm is repeated halving: log2(n) counts how many times you can halve n before reaching 1. Going from n = 1000 to n = 1,000,000 multiplies the input by a thousand, yet log2(n) only rises from about 10 to about 20. That is the secret of binary search: doubling the haystack adds just one more probe.
Theta(n), linear time, is the natural cost of touching every element once: scanning a list, summing an array, finding a maximum. It is often the best you can hope for when the answer genuinely depends on all of the input, since you cannot certify it without at least reading everything. Between log and linear sits Theta(sqrt n), the square root — slower than logarithmic, faster than linear — which surfaces in tricks like block decomposition, where you split n items into about sqrt n blocks of about sqrt n each. It is the rarer animal in the zoo, but worth knowing it lives between its two famous neighbours.
The workhorse middle: linearithmic and the polynomials
Just above linear sits Theta(n log n), linearithmic time — the running time of the best general comparison sorts like merge sort. It is only a whisker slower than linear: for n = 1,000,000 the log factor is about 20, so n log n is roughly twenty times n, not twenty thousand times. Crucially, n log n is much closer to n than to n^2; treating an n log n sort as "basically linear" is a fair working intuition, while treating it as "basically quadratic" badly overestimates the cost. This is the floor that the comparison-sorting lower bound says you cannot beat with comparisons alone.
Then come the polynomials: Theta(n^2) for a pair of nested loops, Theta(n^3) for a triple nest like naive matrix multiplication, and higher powers beyond. Within polynomials the rule is simply that the larger exponent wins for large n — n^3 eventually dwarfs n^2 by any factor — and the sum and product rules tell you how to combine them: in a sum, the biggest term swallows the rest (n^2 + 5n + 99 is Theta(n^2)), while running one loop inside another multiplies their costs. These two rules are most of the everyday arithmetic of reading running times.
The cliff: exponential and factorial
Past every polynomial lies a cliff. Theta(2^n), exponential time, is the cost of trying all subsets of n items — and it does not grow, it detonates. Each extra element doubles the work, so 2^n goes 1024 at n = 10, about a million at n = 20, about a billion at n = 30. A polynomial like n^3 at n = 30 is only 27,000; the gap is already astronomical and widening every step. This is the polynomial-versus-exponential divide, the single most important line in the whole zoo, and we will see in a later rung that it is the line between problems we call tractable and those we generally do not.
And beyond even that howls Theta(n!), factorial time, the cost of trying all orderings (permutations) of n items — the naive way to attack the travelling salesman by checking every route. Factorial outruns 2^n because n! = 1 * 2 * 3 * ... * n multiplies by an ever-larger factor each step while 2^n only ever multiplies by 2. By n = 20, n! is already over two quintillion (2.4 * 10^18), while 2^20 is a mere million. If a method enumerates permutations, it is usable only for tiny n, full stop.
n log2 n n^2 2^n n! 10 ~3.3 100 1,024 3,628,800 20 ~4.3 400 1,048,576 2.4 x 10^18 50 ~5.6 2,500 ~1.1 x 10^15 ~3.0 x 10^64 100 ~6.6 10,000 ~1.3 x 10^30 ~9.3 x 10^157
How to compare two animals on the spot
You will not always face a function already in the lineup; sometimes you must compare two unfamiliar ones, like n^2 versus n * (log n)^3, or 2^(sqrt n) versus n^5. The reliable tool is the ratio test you met with the limit view: form the ratio f(n)/g(n) and ask where it heads as n grows. If it tends to 0, then f = o(g) and g wins; if it tends to infinity, f wins; if it settles at a positive constant, they are the same Theta class. The whole hierarchy is just this comparison applied to the common shapes.
- Strip constants and lower-order terms first: 3n^2 + n becomes n^2, since asymptotics ignores both.
- Sort each side by family: powers of n dominate powers of log n, and exponentials dominate every polynomial.
- If both are exponential-ish, compare the exponents themselves: 2^(sqrt n) versus 2^n reduces to sqrt n versus n, so 2^n wins.
- If a quick comparison is still unclear, take the ratio f(n)/g(n) (or compare logarithms of both) and see whether it tends to 0, a positive constant, or infinity.
What the lineup hides — and what it really means
The hierarchy is a statement about large n, and only about large n. Because asymptotics only kicks in past some threshold, a method that is asymptotically higher in the zoo can genuinely win for small inputs, where the dropped constants dominate. A Theta(2^n) routine with a tiny constant can beat a Theta(n^3) routine with a huge constant up to some crossover n, and only past that point does the exponential's doom take over. The lineup tells you who wins eventually, never who wins at n = 8 — that depends on the very constants the notation throws away.
Still, the single most consequential cut in this whole picture is the one between polynomial and exponential. Everything Theta(n^k) for a fixed k we informally call efficient, and everything 2^n and beyond we call intractable in the worst case — that is the practical meaning of the cliff. The distinction is robust precisely because it survives the constants: no fixed constant can rescue 2^n from eventually losing to n^100, and no constant can push n^100 above 2^n forever. The polynomial-exponential boundary is the gradient that the rest of this ladder, all the way up to P versus NP, is built around.