recategorized by
590 views
2 votes
2 votes

the definition  of big O and Big omega notation difference given in coreman is quite confusing   so if someone can explain in clear way 

and e.g is function is like   x3+4x2+700x+30  then its big O notation will be O(x3)  but what will be its big omega notatiion and how

recategorized by

1 Answer

Best answer
7 votes
7 votes

Formally

  1. 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}$
  2. 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

  1. $T(n)$ is $O(f(n))$  basically means that f(n) describes the upper bound for $ T(n)$ for large $n$
  2. $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})$

selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
2 answers
2
3 votes
3 votes
3 answers
3
Sayan Das 1 asked Sep 21, 2016
801 views
0 votes
0 votes
2 answers
4
saumya mishra asked Jun 26, 2018
360 views
Explain b and c part???