Let $f:\posints\longrightarrow \reals$ and $g:\posints\longrightarrow\reals$ be functions. We write $f=O(g)\text{,}$ and say $f$ is “Big Oh” of $g\text{,}$ when there is a constant $c$ and an integer $n_0$ so that $f(n)\le cg(n)$ whenever $n>n_0\text{.}$ Although this notation has a long history, we can provide a quite modern justification. If $f$ and $g$ both describe the number of operations required for two algorithms given input size $n\text{,}$ then the meaning of $f=O(g)$ is that $f$ is no harder than $g$ when the problem size is large.
We are particularly interested in comparing functions against certain natural benchmarks, e.g., $\log\log n\text{,}$ $\log n\text{,}$ $\sqrt{n}\text{,}$ $n^\alpha$ where $\alpha\lt 1\text{,}$ $n\text{,}$ $n^2\text{,}$ $n^3\text{,}$ $n^c$ where $c>1$ is a constant, $n^{\log n}\text{,}$ $2^n\text{,}$ $n!\text{,}$ $2^{n^2}\text{,}$ etc.
For example, in Subsection 3.5.2 we learned that there are sorting algorithms with running time $O(n\log n)$ where $n$ is the number of integers to be sorted. As a second example, we will learn that we can find all shortest paths in an oriented graph on $n$ vertices with non-negative weights on edges with an algorithm having running time $O(n^2)\text{.}$ At the other extreme, no one knows whether there is a constant $c$ and an algorithm for determining whether the chromatic number of a graph is at most three which has running time $O(n^c)\text{.}$
It is important to remember that when we write $f=O(g)\text{,}$ we are implying in some sense that $f$ is no bigger than $g\text{,}$ but it may in fact be much smaller. By contrast, there will be times when we really know that one function dominates another. And we have a second kind of notation to capture this relationship.
Let $f:\posints\longrightarrow \reals$ and $g:\posints\longrightarrow\reals$ be functions with $f(n)>0$ and $g(n)>0$ for all $n\text{.}$ We write $f=o(g)\text{,}$ and say that $f$ is “Little oh” of $g\text{,}$ when $\lim_{n\rightarrow\infty}f(n)/g(n)=0\text{.}$ For example $\ln n=o(n^{.2})\text{;}$ $n^\alpha=o(n^{\beta})$ whenever $0\lt \alpha\lt \beta\text{;}$ and $n^{100}=o(c^n)$ for every $c>1\text{.}$ In particular, we write $f(n)=o(1)$ when $\lim_{n\rightarrow\infty}f(n)=0\text{.}$