Salve a tutti. Sto studiando l'analisi della complessità di un
algoritmo, ma facendo il calcolo non trovo gli stessi risultati della
teoria. La relazione di ricorrenza da cui partono è:

T(N,M,B)=
THETA(N/B) se N <= M
2*T(N/2,M,B) + THETA(N/B) se N > M

il risultato dovrebbe essere:

THETA(N/B*(log(N/M)+1))

però facendo il calcolo deduco:

T(N,M,B)=2^i*T(N/2^i,M,B)+i*THETA(N/B)

a questo punto mi trovo che arrivo al caso base quando:

i=log(N/M)

e quindi sostituendo non mi trovo lo stesso risultato ottenuto nella
teoria. Mi sapreste indicare per caso dove ho commesso l'errore? Lo'ho
fatto pià volte ma ottengo sempre lo stesso risultato sbagliato.
Grazie mille.

Luca