Results 1 to 4 of 4

Math Help - "order of" equality question

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    10

    Unhappy "order of" equality question

    Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by inneedofhelp View Post
    Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
    what do you mean by O(g(n)) and O(h(n))?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Jhevon View Post
    what do you mean by O(g(n)) and O(h(n))?
    He means the big O notation.*
    (I am too lazy to post proofs now).



    *)I hate that notation with a love.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by inneedofhelp View Post
    Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
    f(n)=O(g(n)) means there exist n_1 and M_1 such that:

    |f(x)| \le M_1|g(n)|\ \forall n>n_1

    and g(n)=O(g(n)) means there exist n_2 and M_2 such that:

    |g(x)|\le M_2|h(n)|\ \forall n>n_2

    Hence:

    |f(x)|\le M_1 M_2 |h(n)|\ \forall n> \max(n_1,n_2)

    Therefore f(n)=O(h(n))

    RonL
    Last edited by CaptainBlack; September 3rd 2007 at 09:31 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 17th 2011, 02:50 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum