the growth-rate hierarchy

Not all 'getting bigger' is equal. Some costs barely budge as the input grows, some climb steadily, and some explode. The growth-rate hierarchy is the standard ranking of the common cost functions from gentlest to most violent, so that at a glance you can tell which of two algorithms will eventually win.

From slowest-growing (best) to fastest-growing (worst), the usual ladder is: constant Theta(1); logarithmic Theta(log n); linear Theta(n); linearithmic Theta(n log n); quadratic Theta(n^2); cubic Theta(n^3); more generally polynomial Theta(n^k) for fixed k; exponential Theta(2^n) (or any base above 1); and factorial Theta(n!), which is even worse than exponential. Each entry is little-o of the next: log n = o(n), n = o(n log n), n log n = o(n^2), n^k = o(2^n) for every fixed k, and 2^n = o(n!). To feel the gaps, take n = 1000: log n is about 10, n is 1000, n log n is about 10000, n^2 is a million, 2^n has about 300 digits, and n! is astronomically larger still.

This ladder is the mental map behind 'efficient'. A jump from one rung to a lower one can turn an overnight computation into an instant one. The most consequential boundary on the ladder is between polynomial and exponential: polynomials, however high their degree, are eventually dwarfed by any exponential, which is why polynomial time is the dividing line for 'tractable'. One caveat the ladder hides: these are asymptotic rankings, so for small n the order can be scrambled by constants — but as n grows, the ladder always reasserts itself.