Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need Help Make sure of Order

  1. Sep 21, 2008 #1
    Hello All, I need help making sure I am right about this. Say for example I have these two functions: f(n) = 2^n and g(n) = 3^n.

    Now the order is O(2^n) and O(3^n) respectfuilly. Now I need make sure I am right about this: based on the order, O(2^n) < O(3^n) therefore f(n) < THETA(g(n)).

    Is this statement correct here when I say f(n) < THETA(g(n)) and that O(2^n) < O(3^n)?
    Last edited: Sep 21, 2008
  2. jcsd
  3. Sep 22, 2008 #2
    Isn't O(2^n) = O(3^n)? Exponential functions differ by a multiplicative constant.
  4. Sep 22, 2008 #3


    User Avatar
    Science Advisor

    The constant C does not exist such that [tex]C \cdot 2^x > 3^x[/tex] for all x.
  5. Sep 22, 2008 #4
    Ack. My intuition failed me. I was thinking of 2x^n versus 3x^n for a constant n. Sry.
  6. Sep 22, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    O(2^n) is O(3^n) in the usual abuse of notation sense. But the set of functions that are O(2^n) is a proper subset of the set of functions that are O(3^n). For example, 2.0001^n is not O(2^n).

    "f(n) < THETA(g(n))" isn't defined -- O, o, Theta, and the others use only the element operator (or, by the abuse mentioned above, an equal sign). Do you perhaps mean that 2^n is o(3^n)? That would be correct, because lim 2^n/3^n = 0.
  7. Sep 22, 2008 #6
    Thank You all. I was able do what CRGreathouse with the limits which made more since to me. From what the professor was saying, I am thinking that Theta is a value that is im between the upper and lower bound, and I need to show whether or not the functions where less than the upperbond (f(n) < theta (g(n)) ), greater than the lower bound (f(n) > theta (g(n)) ), or equal ((f(n) = theta (g(n)) )). I hope that make sense (I'm not a genius when it comes to wording in math). Just like to say thanks again for all your input. It helped.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook