Asymptotic Notation

Appendix A Asymptotic Notation

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{.}\)

🔗

Example A.0.1.

If \(f(x)=x^2-12x\text{,}\) \(g(x)=x^3\) and \(h(x)=7x-3\text{,}\) then the following are true

\(f=O(g)\text{,}\)
🔗

🔗
\(f=o(g)\text{,}\)
🔗

🔗
\(g=\Omega(f)\text{,}\)
🔗

🔗
\(fh = \Theta(g)\text{,}\)
🔗

🔗
\(f=(1+o(1))x^2\text{,}\)
🔗

🔗
\(gh \sim 7x^4\text{,}\)
🔗

🔗
\(h=o(e^x)\text{,}\)
🔗

🔗
\(\sin(x) = o(h)\text{,}\)
🔗

🔗
\(\sin(x) + 100 = \Theta(1)\text{,}\)
🔗

🔗
\(e^{-x}-4 = \Theta\left(\frac{x^2-6}{7x^2+2x-200}\right)\text{,}\)
🔗

🔗
\(f=o(x^2\log(x))\text{,}\)
🔗

🔗
\(1/f = o(1)\text{,}\)
🔗

🔗
\(1/g = \Omega(e^{-x})\text{.}\)
🔗

🔗

🔗

Example A.0.2.

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.

🔗

Prev Top Next