Quelle est la grosse notation de $ o $ d'une somme d'un journal?

Question

pour: $$ \ somme ^ {n + m} _ {i= n} \ journal (i) $$ Je me demande quelle est la grosse notation et comment le prouver ... Je crois que nous pouvons aussi écrire cela comme $$ \ journal (n) + \ journal (n + 1) + \ journal (n + 2) + \ ldots + \ log (n + m) $$

aussi $$ \ journal (n + m)! / \ journal (n-1)! $$

merci

Answer 1

Rappelez que la somme de $ \ log $ est équivalente à la $ \ log $ des produits.

c'est:

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

Nous pouvons donc changer votre fonction:

$$ \ commencer {align} \ sum_ {i= n} ^ {n + m} \ journal i &=journal \ prod_ {i= n} ^ {n + m} i \\ &=journal (N \ CDOT (N + 1) \ CDOT (N + 2) \ CDOT \ LDOT \ CDOT (M-1) \ CDOT M) \\ &=journal (m! \ / \ (n-1)!) \\ \ fin {align} $$

Ensuite, nous pouvons également utiliser la règle de la division pour les récupérer:

$$ \ journal (m! \ / \ (n-1)!)=journal (m!) - \ journal ((N-1)!) $$

Ensuite, en utilisant approximation de Stirling Nous pouvons voir immédiatement:

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

Vous pourrez peut-être faire mieux cependant en prenant des limites plus précises pour obtenir:

$$ \ commencer {align} \ journal (m!) - \ journal ((N-1)!) & \ Leq em ^ {m + \ frac {1} {2}}} ^ {- m} - \ sqrt {2 \ pi} (n -1) ^ {n- \ frac {1} {2}} e ^ {1-n} \\ &=vdots \ fin {align} $$

Answer 2

O ((m +1) journal (n + m)).C'est évidemment une limite supérieure.Mais aussi la plupart des valeurs ont un logarithme proche du maximum, c'est donc aussi une bonne liaison inférieure.

Dans votre cas particulièrement simple, la formule STRIling vous donnera un meilleur résultat, mais vous avez demandé à Big-O uniquement.