Results 1 to 3 of 3

Math Help - Big O proof

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    57

    Big O proof

    I'm having trouble with this proof:

    Show that if p(n) is a polynomial in n, then \log{p(n)} is O(\log{n}).

    I'm given this definition for O(n):

    T(N) = O(f(N)) if there are positive constants c and n_0 such that T(N) \leq cf(N) when N \geq n_0.

    I'm not sure how to use it to arrive at the conclusion that \log{p(n)} = O(\log{n}). Wouldn't \log{p(n)} always be greater than \log{n}?

    Any help would be much appreciated,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2009
    Posts
    57
    I've been thinking about it more. Would this be sufficient?

    We can approximate p(n) to be n^k, where k is the highest degree in p(n). We notice that p(n) is O(n^k). Next, we observe that \log{n^k} = k\log{n}. Therefore, \log{p(n)} = k\log{n}, so \log{p(n)} = O(\log{n}).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by centenial View Post
    I'm having trouble with this proof:

    Show that if p(n) is a polynomial in n, then \log{p(n)} is O(\log{n}).

    I'm given this definition for O(n):

    T(N) = O(f(N)) if there are positive constants c and n_0 such that T(N) \leq cf(N) when N \geq n_0.

    I'm not sure how to use it to arrive at the conclusion that \log{p(n)} = O(\log{n}). Wouldn't \log{p(n)} always be greater than \log{n}?

    Any help would be much appreciated,
    We know that there exists some C and some N such that N\leqslant n\implies p(n)\leqslant Cn^{k}. And clearly there exists some N' such that N'\leqslant n\implies Cn^{k}\leqslant n^{k+1} and so N'\leqslant n\implies p(n)\leqslant n^{k+1}\implies \log p(n)\leqslant (k+1)\log  n
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum