Formally
- T(n) is $O(f(n))$ iff some constants c and $n _{0}$ $T(n)\leq c f(n)$ for all $n\geq n _{0}$
- T(n) is $\Omega(f(n))$ iff some constants c and $n _{0}$ $T(n) \geq c f(n)$ for all $n\geq n _{0}$
Informally
- $T(n)$ is $O(f(n))$ basically means that f(n) describes the upper bound for $ T(n)$ for large $n$
- $T(n)$ is $\Omega(f(n))$ basically means that f(n) describes the lower bound for $ T(n)$ for large $n$
Given function $T(x) x^{3}+4x^{2}+700x+30$
Big-O
$x^{3} \leq x^{3}$
$x^{3}+4x^{2}\leq x^{3}+x^{3}$
$x^{3}+4x^{2}+700x \leq x^{3}+x^{3}+x^{3}$
$x^{3}+4x^{2}+700x+30\leq x^{3}+x^{3}+x^{3}+x^{3}$
$x^{3}+4x^{2}+700x+30\leq 4 x^{3} $
c= 4 and $f(n)$ is $O( x^{3} ) $
Well given function $T(x)$ is also $O( x^{4} ) $ , $O( x^{100} ) $ , $O( 2^{n} ) $, $O( x^{x} ) $ . We take the closest upper bound . We call that function as asymptotically closest .
Hence $ T(x)$ is $O\left( x^{3}\right) $ Big -O
and
$ T(x)$ is $o\left ( x^{4}\right) $ Little - O (strictly lesser)
Big- Omega
$x^{3}+4x^{2}+700x+30 \geq 1 $
$x^{3}+4x^{2}+700x+30\geq x^{2} $
$x^{3}+4x^{2}+700x+30\geq x^{3} $
Given function $T(x)$ is also $\Omega(1)$ , $\Omega(x^{2})$ ,$\Omega(x^{3})$. We take the closest lower bound . We call that function as asymptotically closest .
Hence $T(x)$ is $ \Omega(x^{3})$ Big Omega
T(x) is little-omega $\omega \left( x^{2} \right)$
here f(x) = $x^{3}$ best describes exact bound for T(n) . hence we can also say that $T(x)$ is $\Theta(x^{3})$