1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: What is the order of these functions

  1. Sep 21, 2008 #1
    I need now what is the order (The Big Oh notation) of these three functions:

    Last edited: Sep 21, 2008
  2. jcsd
  3. Sep 21, 2008 #2


    User Avatar
    Science Advisor

    Your question is incomplete. You need to specify x ->?.
  4. Sep 21, 2008 #3


    User Avatar
    Science Advisor

    Also you should specify what your definition of "order" is. The "big Oh" I am familiar with says that one function is "O" of another function. Saying that g(x) is O(f(x)) (as x -> a) means that [itex]\lim_{x\rightarrow a} g(x)/f(x)[/itex] is a finite number.

    Often "order" is given in terms of x going to infinity but even so, your question makes no sense. A function does not just have an "order". It is or is not "O" of another function. Are you asking if 2x= O(3x) or vice-versa?
    Last edited by a moderator: Sep 22, 2008
  5. Sep 21, 2008 #4
    Good point guys. I wanted to compare two of them to each other, lets say:

    f(x) = 2^x vs. g(x) = 3^x

    now from this I have to determine if f=Theta(g), f<Theta(g) or f>Theta(g). Instead of using L'Hospital rule:

    c=lim 2^x/3^x = lim (2/3)^x = 0 as x goes to infinite this would mean that f<Theta(g).

    I wanted to do this using order where x>1. Would 2^x have O(2^x) and 3^x have O(3^x), where f(n)<g(n)?
  6. Sep 22, 2008 #5


    User Avatar
    Science Advisor

    Please don't shift from O(g) to "Theta(g)"!

    And since that limit is 0, f(x)= o(g). "Small o" or f= o(g) means that the fraction f/g goest to 0. As I said before, most text books give: "f= O(g), as x goes to a" means that f(x)/g(x) goes to a finite limit" which includes 0 so if f(x)= o(g), it follows that f= O(g). Some text books however, require that f(x)/g(x) go to a [g]nonzero[/b] finite limit in order that f= O(g) so that does NOT include f= o(g). I recommend that you check the definition in your text book to be certain which convention it uses.

    Oh, and to answer your last question, f= O(f) for any function f so saying "2x= O(2x" (which is what I guess you mean by "2^x have O(2^x)) so "2x= O(2x)" is trivially true. A function doesn't have "an order" except as compared to some other function.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook