Results 1 to 3 of 3

Math Help - Time complexity Help

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    mirtam
    Posts
    1

    Time complexity Help

    Hi,

    I'm struggling with these 2 questions:
    Time complexity Help-untitled-2.jpg


    I'm trying to understand what should i prove here and what is the approach for solving that?

    Q1: both expressions are O(nlogn) ?
    Q2: ??


    Tnx,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Time complexity Help

    Quote Originally Posted by zevelBen View Post
    I'm trying to understand what should i prove here and what is the approach for solving that?
    In a), you should say whether the following statements hold: log(n!) = O(nlog(n)), nlog(n) = O(log(n!)) and similarly with Θ and Ω replacing O.

    Quote Originally Posted by zevelBen View Post
    Q1: both expressions are O(nlogn) ?
    Yes, but you can not only bound both functions from above by nlog(n), you can also bound log(n!) from below by nlog(n), i.e., log(n!) = Θ(nlog(n)). This means that all six statements hold for these two functions.

    Showing log(n!) ≤ nlog(n) is easy using properties of log. For log(n!) = Ω(nlog(n)) use a bound related to Stirling's approximation: n!\ge n^ne^{-n}\sqrt{2\pi n}.

    For b), simplify both sides using the fact that ln(x) and e^x are mutually inverse.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    639
    Thanks
    257

    Re: Time complexity Help

    Hi,
    I assume you know calculus. The following are very often useful:
    Let f(n) and g(n) be non-negative functions. Assume
    \lim_{n\rightarrow\infty}{f(n)\over g(n)}=L

    1. If L\neq0 then f(n)=\Theta(g(n)) and so also f(n)=O(g(n)) and f(n)=\Omega(g(n)).

    2. If L=0, then f(n)=O(g(n)), but f(n)\neq\Omega(g(n)) (and so f(n)\neq\Theta(g(n))

    Both 1) and 2) are easy consequences of the definition of limit and the orders.

    Example:
    Recall \int \text{ln}(x)\,dx=x\text{ln}(x)-x and so \int_1^n \text{ln}(x)\,dx=n\text{ln}(n)-n+1
    By approximating Riemann sums and the fact that ln is increasing,

    \sum_{k=1}^{n-1}\text{ln}(k)\leq\int_1^n \text{ln}(x)\,dx\leq\sum_{k=2}^{n}\text{ln}(k)

    With a little more argument, you can see that

    \lim_{n\rightarrow\infty}{\sum_{k=1}^{n}\text{ln}(  k)\over n\text{ln}(n)}=\lim_{n\rightarrow\infty}{n\text{ln  }(n)-n+1\over n\text{ln}(n)}=1; i.e. \lim_{n\rightarrow\infty}{\ln(n!)\over n\ln(n)}=1

    So by 1), \ln(n!)=\Theta(n\ln(n))
    Last edited by johng; November 17th 2013 at 07:46 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Calculate time complexity of modular arithmetic
    Posted in the New Users Forum
    Replies: 3
    Last Post: January 20th 2013, 12:00 AM
  2. Calculate time complexity of modular arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 19th 2013, 11:58 PM
  3. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  4. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 06:55 AM
  5. What is the Computional Complexity of this ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2009, 04:04 AM

Search Tags


/mathhelpforum @mathhelpforum