Intuition on Polynomial Running Times

The quadratic function $f(n) = n^2$ is a common growth rate in computer science. How does it grow, intuitively? I’ve found it useful to think about the function in terms of what happens when you double the size of the input $n$. In the case of the quadratic function, doubling the input size always multiples the running time by a factor of four. The proof is short: $f(2n) / f(n) = (2n)^2 / n^2 = 4n^2 / n^2 = 4$. Generalizing, multiplying the input by a factor of $k$ multiplies the running time by a factor of $k^2$.

This property continues to hold even if there is some constant factor $a$ so that the function has form $f(n) = an^2$. We may want to also consider lower-order terms, making the function of the form $f(n) = an^2 + bn + c$. Now the above property still holds when $n$ is large enough that the lower-order terms $bn + c$ become insignificantly small compared to the term $an^2$. More formally: $$\lim_{n \rightarrow \infty} \frac{f(kn)}{f(n)} = \lim_{n \rightarrow \infty} \frac{a \cdot (kn)^2 + b \cdot (kn) + c}{an^2 + bn + c} = k^2 \; .$$

I find it useful that this property always eventually holds for any quadratic irrespective of what the values of $a,b$ and $c$ are. How to use this result in practice? Suppose you have run an algorithm with a quadratic run time on a test set that is 5% of your whole input, and it took 1 hour. How long does it take to run the whole data set? Your whole input is $20$ times larger, so it will take $20^2 = 400$ times as long, that is, 400 hours given that the input is large enough so that the lower order terms do not matter.

Past quadratic

Ok then, what about the cubic function $f(n) = n^3$? Now multiplying the input by $k$ multiplies the running time by $k^3$. More generally, if the function is of the form $f(n) = n^d$, then multiplying the input by a factor $k$ multiplies the running time by a factor $k^d$.

Suppose we are benchmarking some algorithm, which we know has a polynomial running time, but do not know which degree. To figure out the degree of the polynomial, we could try to fit different polynomial curves on the running time, but there is an easier way. We can run the algorithm on two large inputs of sizes $n$ and $2n$, infer the polynomial degree from the property above. For example, if the running time increased by a factor 8, we know the function is cubic. More generally, if we run the above experiment, and the running time increases by a factor $r$, then the degree of the polynomial is $\log_2 r$.