Big O, Omega, Theta Notation

Big-O

Upper bounding a function

$f$ and $g$ real valued functions. $f(n)\in O(g(n))$ if there exists constants $c>0$ and $n_0\ge 0$ such that $0\le f(n)\le c\cdot g(n)$ for all $n\ge n_0$.

Properties

• Reflexivity: $f\in O(f)$
• Constants: If $f\in O(g)$ and $c>0$, then $cf\in O(g)$
• Products: If $f_1\in O(g_1)$ and $f_2\in O(g_2)$, then $f_1{f}_2\in O(g_1{g}_2)$
• Sums: If $f_1\in O(g_1)$ and $f_2\in O(g_2)$, then $f_1+f_2\in O(\max (g_1,g_2))$
• Transitivity: If $f\in O(g)$ and $g\in O(h)$, then $f\in O(h)$

Big-$\Omega$

Lower bounding a function

$f$ and $g$ real valued functions. $f(n)\in \Omega (g(n))$ if there exists constants $c>0$ and $n_0\ge 0$ such that $f(n)\ge c\cdot g(n)\ge 0$ for all $n\ge n_0$.

$f(n)\in \Omega (g(n))⟺g(n)\in O(f(n))$

Big-$\Theta$

Tight bound of a function

$f$ and $g$ real valued functions. $f(n)\in \Theta (g(n))$ if there exists constants $c_1>0$, $c_2>0$ $n_0\ge 0$ such that $0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$ for all $n\ge n_0$.

Asymptotic Bounds

• ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0$ then $f(n)\in O(g(n))$ but not $\Omega (g(n))$
• ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$ then $f(n)\in \Omega (g(n))$ but not $O(g(n))$