Time Complexity Analysis

Review of time limit:

$f=O(g)$ (Big-O): $\exists k\in {\mathbb{R}}_0,(\exists n_0\in \mathbb{N}(\forall n\in \mathbb{N}.(n>n_0⟹f(n)\le kg(n))))$

• we can use big-O to describe functions’ upper bound by some common function where as larger input there exists such $k$ times the function upper the current function
• aka $f\le g$

$f=\Omega (g)$ (Big-Omega): $\exists k\in {\mathbb{R}}_{>0},(\exists n_0\in \mathbb{N}(\forall n\in \mathbb{N}.(n>n_0⟹f(n)\ge kg(n))))$

• we can use big-Omega to describe functions’ lower bound by some common function where as larger input there exists such $k$ times the function lower the current function
• $f\ge g$

$f=\Theta (g)$ (Big-Theta): $\exists k_1,k_2\in {\mathbb{R}}_{>0},(\exists n_0\in \mathbb{N}(\forall n\in \mathbb{N}.(n>n_0⟹k_{1}g(n)\le f(n)\le k_{2}g(n))))$

• There exist another function bounded function in some area $k_1,k_2$ as larger input
• $f=O(g)\wedge f=\Omega (g)⟺f=\Theta (g)$
• $f\approx g$

$f=o(g)$ (Little-o): $\forall k\in {\mathbb{R}}_{>0},(\exists n_0\in \mathbb{N}(\forall n\in \mathbb{N}.(n>n_0⟹f(n)<kg(n))))$

$f=\omega (g)$ (Little-omega): $\forall k\in {\mathbb{R}}_{>0},(\exists n_0\in \mathbb{N}(\forall n\in \mathbb{N}.(n>n_0⟹f(n)>kg(n))))$

$log$ in time limit analysis is always stand for $lo{g}_2$ and we always use $\phi$ to present the golden ratio

$1<log(n)<n^{0.001}<n<nlog(n)<n^{1.001}<n^{1000}<1.001^n<2^n$ for $li{m}_{n\to \infty }$