polynomial vs exponential growth

The single most important contrast in the whole growth hierarchy is between polynomial growth, like n^2 or n^10, and exponential growth, like 2^n. They feel similar when you first meet them, but they are worlds apart: every polynomial, no matter how steep, is eventually crushed by every exponential. This gap is the reason computer scientists divide problems into 'efficiently solvable' and 'not known to be'.

Here is the key fact, stated precisely: for any fixed exponent k and any base b > 1, the limit of n^k / b^n as n goes to infinity is 0. In words, n^k = o(b^n): the polynomial is little-o of the exponential, no matter how large k is or how close to 1 the base b is. The intuition is that exponentials multiply by a constant factor each time n increases by one (2^(n+1) = 2 times 2^n), whereas a polynomial only adds a shrinking fraction; repeated multiplication always overtakes repeated addition. Concretely, n^10 is bigger than 2^n up until around n = 60, but past that the exponential pulls ahead and never looks back, becoming millions and then trillions of times larger.

Why this matters so much: an exponential-time algorithm is usually useless beyond tiny inputs, because adding just one element to the input can double the running time. A polynomial algorithm scales gracefully — doubling the input multiplies the time by a fixed factor (4x for n^2, 8x for n^3). The honest nuance is that 'polynomial' is a coarse label: an n^100 algorithm is polynomial but hopeless in practice, while a 1.001^n algorithm is exponential yet fine for moderate n. The polynomial-exponential line is the right first cut, not the final word.