Results 1 to 2 of 2

Math Help - Omega

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    3

    Omega

    Suppose we have the following 3 functions
    f(n), g(n), h(n)
    such that f(n) = Omega(g(n)) and g(n) = Omega(h(n)). Must it be the case that f(n) = Omega(h(n))? Explain why or give a counterexample.

    My attempt:

    f(n)>= c1g(n) for all n>n1
    g(n)>=c2 h(n) for all n>n2


    So, f(n)>=c1 c2 for all n>min(n1,n2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rola66 View Post
    Suppose we have the following 3 functions
    f(n), g(n), h(n)
    such that f(n) = Omega(g(n)) and g(n) = Omega(h(n)). Must it be the case that f(n) = Omega(h(n))? Explain why or give a counterexample.

    My attempt:

    f(n)>= c1g(n) for all n>n1
    g(n)>=c2 h(n) for all n>n2


    So, f(n)>=c1 c2 for all n>min(n1,n2)
    f(n) = \Omega(g(n)) and g(n) = \Omega(h(n))

    means that there exists n_1, n_2 and c_1>0, c_2>0 such that:

    f(n) \ge  c_1 g(n) \mbox{ for all } n > n_1

    g(n) \ge c_2 h(n) \mbox{ for all } n > n_2

    So:

    f(n) \ge c_1 c_2 h(n) \mbox{ for all } n> \max(n_1,n_2)

    Hence f(n) is \Omega(h(n))

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 25th 2011, 10:46 AM
  2. Big Omega question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 20th 2009, 11:06 AM
  3. dimensions of omega
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: May 19th 2008, 04:59 AM
  4. Big Oh and Big Omega
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 4th 2008, 01:01 AM
  5. Angular Velocity (Omega)
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 6th 2007, 04:49 AM

Search Tags


/mathhelpforum @mathhelpforum