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}$ .

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$ .

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$

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$ .