En el análisis de un algoritmo de esta declaración ha llegado hasta:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ n\log(n) = \log(n^n)$$ and it is easy to see that $\log(n!) \en O(\log(n^n))$, but the "$\Theta$" part is still perplexing. I tried calculating the limit: $$\lim_{n \to\infty} \frac{\log(n!)}{\log(n^n)}$$but the only way that I thought of doing this was to substitute the Stirling approximation in the numerator, and it works, but this would only be justified if $$\lim_{n \to\infty}\frac{\log(n!)}{\log(\sigma(n))} = 1$$(with $\sigma(n) = \sqrt{2\pi} \cdot n^{\frac{1}{2} + n} \cdot e^{-n} $) and is it? It is certainly wrong that $$a_n \sim b_n \ \Rightarrow \ f(a_n) \in \Theta(f(b_n))$$ for a general (continuous) $f : \mathbb{R} \rightarrow \mathbb{R}$, since, for example, $a_n =n^2+n, b_n=n^2$ and $f(x) = e^x$ is a counterexample (since $\frac{n^2 + n}{n^2} \rightarrow 1$, but $ \frac{e^{n^2+n}}{e^{n^2}} \rightarrow +\infty$). Así que aquí están mis preguntas:
- Es la afirmación verdadera, bajo ciertas hipótesis en $f$ (por ejemplo, $f \in O(x)$ sería plausible), y, en particular, en el caso de la $f(x) = \log(x)$?
- Si no, ¿cómo puedo proceder en la prueba inicial, el uso de Stirling, o de otra manera?
No sé (y no quieres usar nada andvanced en la aproximación de Stirling, tales como las estimaciones de error; yo sé que $n! = \sigma(n)(1+ O(\frac{1}{n}))$, y no mucho más.
Cualquier ayuda es muy apreciada. Gracias.