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: Big-O notation

  1. Jun 20, 2008 #1
    1. The problem statement, all variables and given/known data

    1. Prove the following subset relationships:
    a. [tex]Constant \subseteq Logarithmic[/tex]
    b. [tex]Logarithmic \subseteq Linear[/tex]
    c. [tex]n log n \subseteq Polynomial[/tex]
    2. Relevant equations

    O(1) Constant
    O(log n) Logarithmic
    O(n) Linear
    O(n log n) n log n
    O(n^m), m > 1 Polynomial of order m

    3. The attempt at a solution
    a. There exists an c, k element of Z where f(n) =< C * 1, f(n) =< C log n for all n => k.

    So to show that Constant is a subset of Log, I need to show 1 =< C log n, And I find a C and k that satisfies that condition right? C = 1 k = 2

    b. C = 1 k = 1 then log n =< Cn = log 1 =< 1 * 1

    c. C = 1 k = 1 then n log n =< n^2 = 1 log 1 =< 1^2
    Last edited: Jun 20, 2008
  2. jcsd
  3. Jun 23, 2008 #2
    I'm not sure I can help but here goes.. for a, you want to show that after a while,
    f(x) = c <= log n.

    Well easiest way is imo to do lim n->\infty C/Log N = 0. Not sure if that is a proof, so you might consider:

    Log n = C -> 10^c = n -> for n >= 10^c, log n > c. // as log is an increasing function

    for b, you can look at lim n->\infty Log N / N = 0. (or opposite = infitity) but proof wise consider you want to prove log n <= n for all n > some number.

    If you look at the graph, this is true for all of them, maybe use induction?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook