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!

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