Big Omega(Ω) Notation

http://install4install.com

Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time  of function g(n) within a constant factor.

Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.It is used to bound the best case running time of an algorithm.g(n) is an asymptotic lower bound for f(n).

Screen Shot 2014-07-28 at 3.45.31 PM

 

Example 1

  • Prove that if  f(n) = 15n3 + n2 + 4, then f(n) belongs to Ω(n3 ) for all n.
  • For omega notation,c*g(n) should be less than f(n).
  • Here f(n) = 15n3 + n2 + 1
  • g(n) = n3
  • Let c=15
    •  15  n3 <=  15n3 + n2 + 1
    • n=1 
  • f(n) belongs to Ω class.
  • Ω is the lower bound.

Example 2

  • Show that 2n +7 is Ω(n) .
  • f(n) = 2n + 7
  • g(n) = 2n
  • c * g(n) <= f(n)
    • c*2n <=2n+7
    • Let c=2
    • 4n<=2n+7
    • 2n<=7
    • n<=7/2
  • Thus for c=2 and  n0= 7/2 f(n) belongs to Ω(n).

 

 



Short URL: http://tinyit.cc/49f498
Author: Cusp2207 on March 4, 2016
Category: Algorithms, Computer Science
Tags:

Leave a Reply

Last articles