# Thread: Need help understanding a problem with asymptotics and logarithms

1. ## 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 $\displaystyle (\log{n})! = \theta((\log{n})^{\log{n} + \frac{1}{2}}e^{-\log(n)})$

By plugging $\displaystyle (\log{n})!$ into sterling's approximation $\displaystyle n! = \sqrt{2\pi n}(\frac{n}{e})^2$ and use the rules of logarithms to obtain the expression $\displaystyle (\log{n})^{\log{n} + \frac{1}{2}}e^{-\log(n)}$ which is just the result of plugging $\displaystyle (\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 $\displaystyle 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.

2. ## Re: Need help understanding a problem with asymptotics and logarithms

Originally Posted by restin84
By plugging $\displaystyle (\log{n})!$ into sterling's approximation $\displaystyle n! = \sqrt{2\pi n}(\frac{n}{e})^2$
Stirling's approximation is $\displaystyle 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.

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

Originally Posted by restin84
use the rules of logarithms to obtain the expression $\displaystyle (\log{n})^{\log{n} + \frac{1}{2}}e^{-\log(n)}$ which is just the result of plugging $\displaystyle (\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 $\displaystyle \sqrt{2\pi}$ (which $\displaystyle \Theta$ allows) and rewriting $\displaystyle \sqrt{\log n}(\log n)^{\log n}$ as $\displaystyle (\log n)^{\log n+\frac{1}{2}}$.

3. ## 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.