Results 1 to 5 of 5

Math Help - Question on upperbounds of a function

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Question on upperbounds of a function

    If g(n) is a upper bound of f(n), then g(n) is not a lower bound on f(n).

    I think this statement above is false because if f(n) ∈ theta(1), which means the running time of f(n) is constant (ex. f(n) = 1), then this is a counter example of the above statement.
    If c1(g(n)) <= f(n) <= c2(g(n))
    then let g(n), c1, c2 = 1.
    1<=1<=1
    which is true for all n >= x0 for some x0 > 0.

    Is this correct?
    Last edited by Sneaky; January 21st 2013 at 08:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,649
    Thanks
    601

    Re: Question on upperbounds of a function

    Hey Sneaky.

    Can there exist a c2 such that c2 > 1?

    Maybe you should outline what processes have the property where c1 and c2 both equal 1 and then say that the complement of processes of this set of processes don't follow that.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Question on upperbounds of a function

    I don't understand...
    If the upper bound equals the lower bound, doesn't c1 have to equal c2?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,649
    Thanks
    601

    Re: Question on upperbounds of a function

    Yes that is true, but all I'm pointing out for you is to show what processes have this property and which ones don't so you can explain when its true and when its not.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Question on upperbounds of a function

    So for example, if f(n) = n, which is a linear equation, then the upper bound can equal the lower bound right? But I don't understand if there is a function which the upper bound has to equal the lower bound at all times?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trigometric function of a function question.
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: June 12th 2012, 10:03 AM
  2. function inside function proofe question
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 13th 2010, 11:32 AM
  3. Replies: 1
    Last Post: May 30th 2009, 02:59 PM
  4. Replies: 1
    Last Post: August 29th 2008, 10:17 AM
  5. Replies: 2
    Last Post: March 30th 2008, 02:28 PM

Search Tags


/mathhelpforum @mathhelpforum