Ricorrenza - Sostituzione di variabili

[hamming_burst]

EDIT: ho sovrascittto il testo originale per sbaglio, ho salvato solo una parte, cmq non c'era scritto nulla di particolare.


Abbiamo: $T(n) = 2T(sqrt(n)) + log_{2}(n)$ con $sqrt(n)$ ristretto a $ZZ$ (EX Cormen).

sostituisco $log_2(n) = m$ così da avere $n = 2^m$.
riscrivo la ricorrenza $T(n)$ con $T(2^m) = 2T(2^(m/2)) + m$.

definisco $S(k) = T(2^k$, allora $S(m) = T(2^m)$ e riscrivo $S(m) = 2S(m/2) + m$

poi bhe si calcola la complessità $S(m) in O(mlog_{2)(m))$ e si ripristina:
$T(n) = T(2^m) = S(m) = O(mlog_{2}(m)$ = $O(log(n)log(log(n)))$

La riscrittura non mi convince, perchè risulta $S(m/2)$? se fosse $T((2^m)/2)$ potrei esser d'accordo ma così mi manca un passaggio.

Se qualcuno ha voglia di rispiegarmi velocemente che ci sta dietro, ringrazio

[hamming_burst]

Ok, ho risolto. Era banale. Riporto per chi avrà lo stesso dubbio in quel passaggio.

Abbiamo: $T(n)=2T(sqrt(n))+log_2(n)$ con $sqrt(n)$ ristretto a $ZZ$ (EX Cormen).

sostituisco $log_2(n)=m$ così da avere $n=2^m$.
riscrivo la ricorrenza $T(n)$ con $T(2^m)=2T(2^((m/2)))+m$.

definisco $S(k)=T(2^k)$, allora $S(m)=T(2^m)$ e riscrivo $S(m)=2S(m/2)+m$

il passaggio logico è semplicemente considerare a sinistra $k=m$ e a destra $k=m/2$. Punto e fine.