0
$\begingroup$

I'm learning about $\log_2$ for an algorithms class and theres a problem in the book that is confusing me.
It asks:

Find a formula for $\log_2(n!)$ using Stirling's approximation for $n!$, for large $n$.

Stirling's approximation for $n!$ is $\sqrt{2\pi n}(\frac{n}{e})^n$

Does anyone have guidance on how to go about creating this formula?

Thanks

  • 4
    Try to use the formulas $\log (ab) = \log a + \log b$ and $\log (a^n) = n\log a$, good for any basis of the logarithm (check that you understand why they're true first!).2011-02-01
  • 0
    That's exactly what I have but I wasn't sure if that was correct. Seems like it should be more.2011-02-01
  • 1
    Up to terms of order 1/n, you can't really do better than Stirling's formula, so your approach is definitely the right one. By the way, don't forget to adjust your response to base 2.2011-02-01
  • 0
    Usually binary logarithm is lb and lg is decimal logarithm.2011-02-02
  • 2
    @Anixx In complexity theory, lg is base 2 and log is base $e$. Sometimes ln is used for base $e$. What field uses lb and (decimal) lg?2011-02-02
  • 0
    Information theory uses lb and lg was used on calculators and on older logarithmic slide-rules as well as was thought in schools as being decimal logarithm (at least when I studied).2011-02-02
  • 0
    It is also in accord with the ISO standard: http://en.wikipedia.org/wiki/ISO_31-11#Exponential_and_logarithmic_functions2011-02-02
  • 0
    See [Stirling Approximation on wiki](http://en.wikipedia.org/wiki/Stirling%27s_approximation)2012-02-03

1 Answers 1

1

$$\log{n!} \simeq \log{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}=\frac{1}{2}+\frac{1}{2}\log\pi n+n\log n -n\log e=$$

$$\frac{1}{2}(1+\log\pi)-n\log e+\log n \left(\frac{1}{2}+n\right)$$

  • 3
    If that's a hint, then what does a complete solution look like? Oh, by the way, I think you've overlooked the square root (or maybe that's why it's only a hint?).2011-11-05
  • 0
    You're right. Edited.2011-11-05