Results 1 to 3 of 3

Math Help - Need help understanding a problem with asymptotics and logarithms

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Need help understanding a problem with asymptotics and logarithms

    Hi. I have a question for a computer science course. In the problem they manipulate an expression using logarithms.

    They claim that (\log{n})! = \theta((\log{n})^{\log{n} + \frac{1}{2}}e^{-\log(n)})

    By plugging (\log{n})! into sterling's approximation n! =  \sqrt{2\pi n}(\frac{n}{e})^2 and use the rules of logarithms to obtain the expression (\log{n})^{\log{n} +  \frac{1}{2}}e^{-\log(n)} which is just the result of plugging (\log{n})! into sterling's approximation, manipulating the expression, and dropping lower order terms and constants(hence the theta notation). I'm not sure what they are doing to obtain these results. They claim that they apply the rule a^{\log_b c} = c^{\log_b a} I know this is mostly algebraic so forgive me if this is the wrong forum but I figured it would be easier to explain away the missing parts of the final expression.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help understanding a problem with asymptotics and logarithms

    Quote Originally Posted by restin84 View Post
    By plugging (\log{n})! into sterling's approximation n! =  \sqrt{2\pi n}(\frac{n}{e})^2
    Stirling's approximation is n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. Note the power n instead of 2 and ~ instead of =, which means that the limit of the ratio of the two sides tends to 1.

    Quote Originally Posted by restin84 View Post
    They claim that (\log{n})! = \theta((\log{n})^{\log{n} + \frac{1}{2}}e^{-\log(n)})
    It should say \Theta instead of \theta.

    Quote Originally Posted by restin84 View Post
    use the rules of logarithms to obtain the expression (\log{n})^{\log{n} +  \frac{1}{2}}e^{-\log(n)} which is just the result of plugging (\log{n})! into sterling's approximation, manipulating the expression, and dropping lower order terms and constants(hence the theta notation).
    You don't need any manipulation except dropping \sqrt{2\pi} (which \Theta allows) and rewriting \sqrt{\log n}(\log n)^{\log n} as (\log n)^{\log n+\frac{1}{2}}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Need help understanding a problem with asymptotics and logarithms

    I'm sorry for the sloppiness. I'm a little under the gun to get an assignment done and things are not looking up. Thanks for your help. I'll try to be a bit neater next time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Asymptotics
    Posted in the Calculus Forum
    Replies: 0
    Last Post: January 26th 2011, 10:33 AM
  2. Asymptotics.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 21st 2010, 08:25 PM
  3. Asymptotics of a function
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 13th 2008, 08:36 AM
  4. understanding SAT problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: July 30th 2007, 03:04 PM
  5. I'm not understanding this problem
    Posted in the Algebra Forum
    Replies: 5
    Last Post: February 1st 2007, 03:47 PM

Search Tags


/mathhelpforum @mathhelpforum