Module: CS2040S
Week: Week 02
We use big O notation to denote the complexities of growths of certain things. Specifically, in the context of computer algorithms, we use big O notations to measure the time complexities. Below is a function:
$$ f(x) = x^3+2x^2+3x+1 $$
suppose that we want to learn about the order of growth of the function above. We would quickly realize one thing: as $x$ gets greater and greater, the $x^3$ seemed to become the component that contributes the most to the function’s growth, whereas the other components have a less and less contribution. Say, when $x=10$
$$ f(10)=1000+200+30+1=1231 $$
but when we set $x$ to $1000$,
$$ f(1000)=1,002,003,001 $$
the portion of the contribution to the growth by the $2x^2+3x+1$ is now significantly lower. If we further increase $x$, the contribution of these components can be omitted.
BigO Notation
BigO notation is defined as the follows.
For functions $f$ and $g$, if there exists a value $N$ such that for any $n>N$, $f(n)<k\cdot g(n)$ holds true, then $f(n)=O(g(n))$.
This definition may be hard to grasp at first, but it essentially conveys the following things:

BigO notation cares about the large values of $n$, hence, we only need to prove that there exists a value $N$ such that all the values larger than $N$ satisfies the condition;

Contrary to most people’s thoughts, bigO notation cares about the upperbound of the function growth. I.e., it means that the function $f$ grows at most as fast as $g$. It is not a close approximation of the function $f$’s growth.

Because we care most about the growth, we don’t need to show care about the coefficients.
As pointed out in (2), bigO notation only cares about the upperbound of the function growth. Similarly, we have Omega ($\Omega$) notation that denotes the lower bound of a function’s growth.
For functions $f$ and $g$, if there exists a value $N$ such that for any $n>N$, $f(n)<k\cdot g(n)$ holds true, then $f(n)=\Omega(g(n))$.
And we also have Theta ($\Theta$) notation, which fits most people’s perception of the BigO notation, which best describes the growth of the function.
For functions $f$ and $g$ and constants $k_{1}$ and $k_{2}$, if there exists a value $N$ such that for any $n>N$, $k_{1}\cdot g(n)<f(n)<k_{2}\cdot g(n)$ holds true, then $f(n)=\Theta(g(n))$.
Growth Rates
Listed below are a set of growth rates, which are increasing from top to bottom.
Function  Name 

$5$  Constant 
$\log\log (n)$  Double Log 
$\log (n)$  Logarithmic 
$\log^{2}(n)$  Polylogarithmic 
$n$  Linear 
$n\log(n)$  Loglinear 
$n^{3}$  Polynomial 
$n^{3}\log(n)$  
$n^{4}$  Polynomial 
$2^{n}$  Exponential 
$2^{2n}$  
$n!$  Factorial 