Big-O Notation

The Big-O notation gives an upper bound on the growth rate of a function. Given functions $f(n)$ and $g(n)$, we say that $f(n)$ is $O(g(n))$, if there are positive constants $c$ and $n_0$ such that $f(n)\le c\cdot g(n)$ for $n\ge n_0$.

In general, if $f(n)$ is a polynomial of degree $d$ then $f(n)$ is $O(n^d)$.

• Drop lower-order terms.
• Drop constant factor in highest order term.

Examples:

• $2n+10$ is $O(n)$
• $7n-2$ is $O(n)$
• $3n^3+20n^2+5$ is $O(n^3)$
• $3\log n+5$ is $O(\log n)$