Upperbound di una funzione ricorsiva.

[boulayo]

Sto studiando l'algoritmo di Pratt per il test di primalità, allora analizzando la complessità dell'algoritmo il mio libro dice:

Abbiamo che $T(n) <= 2 + k + \sum_{i=1}^k T(p_i)$
dove $p_i$ sono i fattori primi di n-1.
(T(n) sono gli steps totali dell'algoritmo)

Usando questo possiamo trovare un limite superiore per T(n).
E' facile vedere ricorsivamente che per esempio $L(n) = 4 log_2 n - 4$ è un limite superiore in quanto

$T(n)<= 2 + k + \sum_{i=1}^k L(p_i) = $..... Algebra algebra algebra ... $ < 4log_2 n - 4 = L(n) $

ora io mi chiedo...
Ma così facendo non sta dando per scontato all'inizio che L(n) è limite superiore mettendo quel <= nella prima disequazione?
Grazie in anticipo per la chiarificazione.

[boulayo]

Credo di aver trovato da solo il senso di quell'affermazione.
Non ha senso chiedersi i fattori primi di un numero già primo, quindi la sommatoria per il T(p_i) DENTRO la sommatoria è 0.
(Non dico formalmente: so che un primo ha un fattore primo, ovvero se stesso, ma l'algoritmo proibisce che ciò venga tenuto in conto, ed esce prima di aggiungere quel fattore)