Ricorrenza con Sostituzione e Telescoping

[soeca-votailprof]

Salve a tutti ragazzi.....ho la seguente ricorrenza:
T(n)=2T(n-1)+2(n-1)
supponendo[tex]n=\log(m) \Rightarrow n-1=\log(m-1) \Rightarrow n-1=\log \frac {m}{2}[/tex]
[tex]T(m)=2T(\log \frac {m}{2} )+2\log \frac {m}{2}[/tex]
[tex]S(z)=T(\log m)[/tex]
[tex]S(z)=2S(\frac{z}{2}) + 2\frac{z}{2}[/tex]
Uso il teorema Master
[tex]a=2 b=2 f(n)=z[/tex] Secondo caso del teorema Master
[tex]T(n) = O(z\log z)[/tex]
[tex]z=\log m[/tex]
quindi avrei [tex]\log m \log\log m[/tex]
che in sostanza sarebbe [tex]O(n \log n)[/tex]
E' la prima volta che faccio ricorrenze....secondo voi il modo di ragionare è corretto?
Premetto che le possibili soluzioni sono:
1) [tex]O(n^2 \log n )[/tex]
2) [tex]O(n\log n)[/tex]
3) [tex]O(n)[/tex]
4) [tex]O(2^n n)[/tex]

Grazie a tutti.

[apatriarca]

Non capisco il tuo passaggio da \(m-1\) a \(m/2\) nel logaritmo. Mi sembra abbastanza evidente che le due quantità non siano uguali e che il loro logaritmo non sia quindi uguale (essendo il logaritmo strettamente crescente). Anche il risultato non ha comunque senso, come è facile osservare prendendo ad esempio \(T(1) = 1\) e calcolandone qualche valore \(T(2) = 4\), \(T(3) = 12 \), \( T(4) = 30 \)... Cresce più velocemente di \(n^2\) (come è anche possibile osservare facendo una dimostrazione più rigorosa) e non può essere quindi \( O(n \log n) \). In ogni caso abbiamo
\[ T(n) = 2(n-1) + 2T(n-1) = 2(n-1) + 4(n-2) + \dots + 2^{k}(n-k) + \dots + 2^{n-1} + 2^{n-1}T(1) \]
Se supponiamo per comodità che \(T(1) = 1\), abbiamo che
\[ T(n) = 2^{n-1} + \sum_{k = 1}^{n-1} 2^k(n - k) = 2^{n-1} + \sum_{k = 1}^{n - 1} n 2^k - \sum_{k = 1}^{n - 1} k 2^k. \]
Che si può calcolare abbastanza facilmente con la formula della serie geometrica e quella della sua derivata. Ti lascio l'ultimo passaggio ma dovrebbe essere \(O(2^n n)\).