Results 1 to 2 of 2

Thread: Size of functions

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    133

    Size of functions

    Hello Everyone!

    I have a couple of questions:

    (1) is $\displaystyle (\log n!)^3 = O(3n^3+3)$ true?

    (2) is $\displaystyle n^{\log _2 n} = O(2^{\sqrt{n}})$ true?

    I'm going for yes for (2), but have no clue regarding (1)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    For the first one,
    if $\displaystyle (\log n!)^3 \in O(3n^3+3) \subseteq O(n^3)$
    then $\displaystyle (\log n!)^3 \leq C^3n^3$ for some $\displaystyle C$ and $\displaystyle n$ sufficiently large.
    So $\displaystyle \log n! \leq Cn$ or $\displaystyle n! \leq a^{n} $ which is not true for $\displaystyle n$ much larger than $\displaystyle a$. Contradiction.

    For the second one,
    $\displaystyle n^{\log _2 n} = 2^{(\log_2 n)^2}$
    Now show that $\displaystyle (\log_2 n)^2 \in O(\sqrt{n})$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Max size of..
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2010, 07:09 AM
  2. Size!
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: Nov 16th 2009, 03:40 PM
  3. Basis and size
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Nov 15th 2008, 08:03 AM
  4. sample size
    Posted in the Statistics Forum
    Replies: 7
    Last Post: May 12th 2008, 07:22 AM
  5. Pool Size
    Posted in the Geometry Forum
    Replies: 2
    Last Post: May 17th 2007, 07:08 PM

Search Tags


/mathhelpforum @mathhelpforum