Five Common Rules for Analyzing the Runtime

Rule #1

This rule states that multiplicative constants can be omitted:

$c\cdot f\preceq f$.

Examples: $5n^2\preceq n^2$, $\frac{n^2}{3}\preceq n^2$, $7n\preceq n$.

Rule #2

This rule states that out of two polynomials, the one with a larger degree grows faster:

$n^a\prec n^b$ for $0\leq a<b$

Examples: $n\prec n^2$, $\sqrt{n} \prec n^\frac{2}{3}$, $n^2 \prec n^3$, $n^0\prec \sqrt{n}$.

Rule #3

This rule states that any polynomial grows slower than any exponential:

$n^a \prec b^n$ for $a \geq 0$, $b>1$

Examples: $n^3 \prec 2^n$, $n^10 \prec 1.1^n$.

Rule #4

This rule states that any polylogarithm—that is, a function of the form $(\log n)^a$—grows slower than any polynomial:

$(\log n)^a \prec n^b$ for $a, b > 0$

Examples: $(\log n)^3 \prec \sqrt{n}$, $n\log n \prec n^2$

Rule #5

This rule states that smaller terms can be omitted:

$f \preceq g$, then $f+g \preceq g$.

Examples: $n+n^2 \preceq n^2$, $n^9+2^n \preceq 2^n$.