Matematicamente.it

Buonasera, sto studiando per l'esame di crittografia e devo imparare il calcolo della complessità di diversi algoritmi. Ho problemi con:
$n! $
Crivello di Eratostene
$b^m(modn) $
Algoritmo dei passi da bambino e da gigante
Andiamo per gradi e iniziamo dal primo.
Allora io so che devo contare il numero di operazioni elementari quindi, prendiamo ad esempio, $n! $
Questo consiste di operazioni del tipo $j! (j+1)$ con j<n
Quindi basta calcolare la complessità di ogni operazione di questo tipo e poi moltiplicarla per n perché va fatta n volte. Il problema in un calcolo di questo tipo è che sto facendo una moltiplicazione che ha quindi complessità o(log(j!) log(j+1)) ma quanto vale effettivamente log(j!)?

Beh, \(\log (n!) = \sum_{k=2}^n \log k\). Ora per stimare questo... che idee hai?

caulacau ha scritto:Beh, \(\log (n!) = \sum_{k=2}^n \log k\). Ora per stimare questo... che idee hai?

Be dovrei stimare la complessita' della somma che quindi e' la lunghezza del numero piu' grande..?