¿Cuál es la notación de Big- $ $ $ de una resumen de un registro?

Question

para: $$ \ sum ^ {n + m} _ {i= n} \ log (i) $$ Me pregunto cuál es la gran notación o cómo demostrarlo ... Creo que también podemos escribir esto como $$ \ log (n) + \ log (n + 1) + \ log (n + 2) + \ ldots + \ log (n + m) $$

también $$ \ log (n + m)! / \ log (n-1)! $$

gracias

Answer 1

Recordar que la suma de $ \ log $ es equivalente al $ \ log $ de productos.

es decir:

$$ \ log (xy)=log x + \ log y $$

Por lo tanto, podemos cambiar su función:

$$ \ comienzan {align} \ sum_ {i= n} ^ {n + m} \ log i &=log \ prod_ {i= n} ^ {n + m} i \\ &=log (n \ cdot (n + 1) \ CDOT (N + 2) \ CDOT \ LDOTS \ CDOT (M-1) \ CDOT M) \\ &=log (m! \ / \ (n-1)!) \\ \ End {align} $$

Luego, podemos usar de manera similar la regla de la división para recuperar estos:

$$ \ log (m! \ / \ (n-1)!)=log (m!) - \ log ((n-1)!) $$

luego usando aproximación de Stirling Podemos ver inmediatamente:

$$ \ log (m!) - \ log ((n-1)!)= O (m \ log m) $$

Es posible que pueda hacerlo mejor aunque tome límites más precisos para obtener:

$$ \ comienzan {align} \ log (m!) - \ log ((n-1)!) & \ leq em ^ {m + \ frac {1} {2}} e ^ {- m} - \ sqrt {2 \ pi} (n -1) ^ {n- \ frac {1} {2}} e ^ {1-n} \\ &=vdots \ End {align} $$

Answer 2

O ((M +1) Log (N + M)).Obviamente es un límite superior.Pero también la mayoría de los valores tienen un logaritmo cerca del máximo, por lo que también es un buen límite inferior.

En su caso particularmente simple, la fórmula Stirling le dará un mejor resultado, pero solo pidió BIG-O.