Big O notation, sometimes called Landau notation, provides a simple shorthand for comparing the growth rates of different functions. Typically, this notation is used to describe the growth rate as a given parameter tends to infinity. Given two real-valued functions \(f\) and \(g\text{,}\) we write
“Asymptote.”
\(f=O(g)\) (pronounced \(f\) is Big O of \(g\)) to mean that there exists constants \(C>0\) and \(x_0\) such that \(f(x)\leq Cg(x)\) whenever \(x\geq x_0\text{.}\)
\(f=\Omega(g)\) (pronounced \(f\) is Omega of \(g\)) to mean that there exists constants \(c>0\) and \(x_0\) such that \(f(x)\geq cg(x)\) whenever \(x\geq x_0\text{.}\)
\(f=\Theta(g)\) (pronounced \(f\) is Theta of \(g\)) to mean that there exists constants \(C>c>0\) and \(x_0\) such that \(cg(x)\leq f(x)\leq Cg(x)\) whenever \(x\geq x_0\text{.}\)
\(f=o(g)\) or \(f\ll g\) (pronounced \(f\) is little o of \(g\)) to mean that \(\lim\limits_{x\to \infty}\frac{f(x)}{g(x)}=0\text{.}\)
\(f=\omega(g)\) or \(f\gg g\) (pronounced \(f\) is little omega of \(g\)) to mean that \(\lim\limits_{x\to \infty}\frac{f(x)}{g(x)}=\infty\text{.}\)
\(f=(1+o(1))g\) or \(f\sim g\) (pronounced \(f\) is asymptotic to \(g\)) to mean that \(\lim\limits_{x\to \infty}\frac{f(x)}{g(x)}=1\text{.}\)
Of course, there is some redundancy here, as some of these notations can be described in terms of the others. For example, \(f=\Theta(g)\) is the same as \(f=O(g)\) and \(f=\Omega(g)\) and \(f\sim g\) is the same as \(f-g=o(g)\text{,}\) which is the same as \(f-g=o(f)\text{.}\)
ExampleA.0.1.
If \(f(x)=x^2-12x\text{,}\)\(g(x)=x^3\) and \(h(x)=7x-3\text{,}\) then the following are true
In this course, most of the functions that we deal with are combinatorial in nature. Thus, the variable that we are dealing with is usually not \(x\text{,}\) but some parameter of the combinatorial objects that we are considering. Here are some examples of very simple combinatorial facts written in Big O notation:
If \(G\) is a finite graph, then \(|E(G)|=O(|V(G)|^2)\text{.}\)
If \(G\) is a tree, then \(|E(G)|=(1+o(1))|V(G)|\text{.}\)
For fixed \(k\text{,}\) we have \(\binom{n}{k} = \Theta(n^k)\text{.}\)
Big O notation can also be used to compare two functions as the variable tends to a particular value \(c\text{,}\) as opposed to infinity. When doing so, one usually quantifies it by appending “as \(x\to c\)”. For example, one can say that \(1/(x-1)^2 = o(1/|x-1|)\) as \(x\to 1\) or that \(\sin(x)/x = \Theta(1)\) as \(x\to0\text{.}\)
If you would like to do some more reading to solidify your understanding of asymptotics and asymptotic notation, there are many resources that you can find on the internet by doing a search for “Big O notation,” or a similar keyword. Some of what you will find may be helpful and well-written, and some might just add to your confusion. To save yourself some time and effort, you might want to start by reading this objectively well-written chapter of Fleck [114]: Link.
