Visualize Common Rules for Runtime Analysis

Multiplicative constants

Multiplicative constants can be omitted. The following plot visualizes that $n^3$ and $n^3/2$ have the same growth rate.

The larger degree grows faster

Out of two polynomials, the one with a larger degree grows faster. The plot below shows the polynomial functions $n$, $n^2$, and $n^3$ for $1\leq n \leq 50$.

The plot illustrates that $n^3$ grows faster than $n^2$ and $n^2$ grows faster than $n$.

Polynomial grows slower than exponential

Any polynomial grows slower than any exponential. Let’s plot $n^4$ ...