# Need help understanding a problem with asymptotics and logarithms

• Sep 27th 2012, 09:50 AM
restin84
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.
• Sep 27th 2012, 10:50 AM
emakarov
Re: Need help understanding a problem with asymptotics and logarithms
Quote:

Originally Posted by restin84
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
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
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}}$.
• Sep 27th 2012, 11:09 AM
restin84
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.