Results 1 to 3 of 3

Thread: 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 $\displaystyle p(n)$ is a polynomial in $\displaystyle n$, then $\displaystyle \log{p(n)}$ is $\displaystyle O(\log{n})$.

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

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

    I'm not sure how to use it to arrive at the conclusion that $\displaystyle \log{p(n)} = O(\log{n})$. Wouldn't $\displaystyle \log{p(n)}$ always be greater than $\displaystyle \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 $\displaystyle p(n)$ to be $\displaystyle n^k$, where $\displaystyle k$ is the highest degree in $\displaystyle p(n)$. We notice that $\displaystyle p(n)$ is $\displaystyle O(n^k)$. Next, we observe that $\displaystyle \log{n^k} = k\log{n}$. Therefore, $\displaystyle \log{p(n)} = k\log{n}$, so $\displaystyle \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
    22
    Quote Originally Posted by centenial View Post
    I'm having trouble with this proof:

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

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

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

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

    Any help would be much appreciated,
    We know that there exists some $\displaystyle C$ and some $\displaystyle N$ such that $\displaystyle N\leqslant n\implies p(n)\leqslant Cn^{k}$. And clearly there exists some $\displaystyle N'$ such that $\displaystyle N'\leqslant n\implies Cn^{k}\leqslant n^{k+1}$ and so $\displaystyle 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: Jun 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 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: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum