[ASD, Algoritmi] Analisi Ricorrenza - metodo iterativo

[HackAlli]

Salve
Vorrei provare a risolvere tale ricorrenza:
\( T(n)= 2T(\frac{n}{2}) + \theta(n) \)
Che è una nota ricorrenza dell'algoritmo merge-sort per cui \(T(n) = \theta(n \lg_2 n) \)
infatti con il metodo induttivo provando questa soluzione possiamo facilmente dimostrarlo ,ma
provando a svolgerla con il metodo iterativo:
\( T(n)= 2T(\frac{n}{2}) + n =\)
\(= 4T(\frac{n}{4}) + 2n =\)
\(= 8T(\frac{n}{8}) + 3n =\)
\(= 16T(\frac{n}{16}) + 4n =\)
\(= ... =\)
\(=2^iT(\frac{n}{2^i}) + n*\sum_{i=1}^{\infty} i ;\)

Ora \( \frac{n}{2^i} == 1\) quando \( i=\lg_2 n \)
per cui:
\(= 2^{\lg_2 n} T(\frac{n}{2^{\lg_2 n}}) + n*\sum_{i=1}^{\infty} i =\)
\(= n + n*(\frac{n(n+1)}{2}) = \)
\(= n + \frac{1}{2}n^3 + \frac{1}{2}n^2 = \theta(n^3) \)

mi trovo quindi \( T(n) = \theta(n^3) \)
Dove è che sbaglio?

[apatriarca]

La formula generale che hai calcolato è sbagliata per diverse ragioni. Prima di tutto non è chiaro da dove viene la sommatoria fino ad infinito. Ti sei infatti fermato dopo \(i\) iterazioni, per cui il numero di termini prodotti deve necessariamente essere finito. Osservando l'iterazione è poi abbastanza evidente che ad ogni iterazione viene aggiunto un termine uguale a \(n\) e non uguale a \(i\,n\) come sembri fare nei tuoi calcoli. Dopo \(i\) iterazioni avrai quindi qualcosa nella forma:
\[ 2^i \, T(n/2^i) + i\,n. \]
Sostituendo quindi \( i = \log_2 n, \) si ottiene \( n\,T(1) + n\,\log_2 n \) come si voleva dimostrare.

[HackAlli]

Grazie mille ora è tutto molto chiaro

in effetti riprovando ancora mi sono accorto che la sommatoria era sbagliata e che era uguale a
\( T(n)= 2^{\lg_2 n}T(\frac{n}{2^{\lg_2 n}}) + n \sum_{j=0}^{\lg_2 n - 1} 1 \)

che è appunto uguale a:

\( T(n)=\theta(n) + n \lg_2 n=\theta(n\lg_2 n) \)