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

Big oh

  1. Jun 18, 2008 #1
    O(1) is constant
    O(log n to the base 2) is logarithmic
    O(n) linear

    how would you prove that constant is a subset of logartihmic?
  2. jcsd
  3. Jun 18, 2008 #2
    O(1) = O(log_2 1) = O(0)
  4. Jun 19, 2008 #3
    I should have been clearer.

    given "Big-Oh" sets
    O(1): constant
    O(log2(n)): logarithmic
    O(n): linear
    O(nlog2(n)): n log n
    O(n^2): quadratic
    O(n^3): cubic
    O(n^m), m>1: polynomial of order m
    O(c^n), c>1: exponential
    O(n!): factorial

    Constant is a subset of logarithmic
    logarithmic is a subset of linear
    n log n is a subset of polynomial
    exponential is a subset of factorial

    Thank you
  5. Jun 19, 2008 #4
    Most follow fairly easily from the definition of Big-Oh. For instance let f be an arbitrary function in O(1). We now wish to show that f is in [tex]O(\log_n(n))[/tex]. Because of the definition of O(1) there exist some [tex]x_0[/tex] and M such that [tex]f(x) \leq M[/tex] for all [tex]x > x_0[/tex]. Now let [tex]x_1 = \max(x_0,n)[/tex] then [tex]f(x) \leq M \leq M\log_n(x)[/tex] for all [tex]x > x_1[/tex] so [tex]f(x) = O(\log_n(n))[/tex]. Here we took advantage of the fact that the logarithm is increasing and [tex]\log_n(x) \geq 1[/tex] when [tex]x \geq n[/tex].

    If you have problems with any specific steps you should post the specific problem you're having.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook