Qual é o Big- $ O $ Notação de uma soma de um log?

Question

para: $$ \ sum ^ {n + m} _ {i= n} \ log (i) $$ Eu estou querendo saber o que é a notação geral do O e como provar isso ... Eu acredito que também podemos escrever isso como $$ \ log (n) + \ log (n + 1) + \ log (n + 2) + \ lDOts + \ log (n + m) $$

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

obrigado

Answer 1

Lembre-se de que a soma da $ \ log $ é equivalente à $ \ log $ de produtos.

isto é:

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

Assim, podemos alterar sua função:

$$ \ begin {alinhar} \ sum_ {i= n} ^ {n + m} \ log i &=log \ prod_ {i= n} ^ {n + m} i \\ &=log (n \ CDOT (N + 1) \ Cdot (N + 2) \ Cdot \ LDOT \ Cdot (M-1) \ CDOT M) \\ &=log (m! \ / \ (n-1)!) \\ \ fim {alinhar} $$

Então podemos usar da mesma forma a regra de divisão para obter estas de volta:

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

Então, usando Aproximação de Stirling Podemos ver imediatamente:

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

Você pode ser capaz de fazer melhor embora, tomando limites mais precisos para obter:

$$ \ begin {alinhar} \ 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 \ fim {alinhar} $$

Answer 2

o ((m +1) log (n + m)).É obviamente um limite superior.Mas também a maioria dos valores tem um logaritmo próximo ao máximo, por isso também é um bom limite inferior.

Em seu caso particularmente simples, a fórmula de Stirling lhe dará um resultado melhor, mas você pediu apenas para o Big-O.