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
    10
    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 10:31 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum