Prueba pertenece que $\sum\limits_{i=1}^k \log(i)$ $O(k)$

Question

Estoy estudiando la complejidad de tiempo del binomio montones y hay una sola operación (operación de hacer montón) que no tiene sentido para mí a menos que lo siguiente es cierto.

$\sum\limits_{i=1}^k \log(i)$ pertenece a $O(k)$

Por favor me ayudar a encontrar una prueba de esa declaración.

Cualquier ayuda apreciada.

Answer 1

Bueno, lo siento pero esto es un $O\left( \int_1^k \log x\mathrm d x\right)$ %#% $ #%

Answer 2

Elvis respuesta es mejor que este, pero ya que la pregunta viene de la introducción de algoritmos, me gustaría señalar que para muchos de primaria CS aplicaciones de la trivial límites como: $$ (n/2)\log(n/2) = (n/2)(\log n - 1) \le \sum_{i=1}^n \log i\le n\log n $$ son lo suficientemente buenos y vale la pena probar si sólo estás haciendo la tarea.

Actualización: El límite inferior de aquí se puede obtener al darse cuenta de que la mitad de los términos de la suma son, al menos,$\log(n/2)$, ya que el registro es monótono. Además, fija caído un conjunto de soportes.