Ricorrenza lineare - non capisco un passaggio

BoG3
Ciao a tutti, non capisco un passaggio di una ricorrenza lineare:

$T(n) = 2T(n^(1/2)) + log n$ poi pongo

$n = 2^m$ e ottengo $T(2^m) = 2T((2^m)^(1/2)) + log (2^m) = 2T(2^(m/2)) + log (2^m)$ e fin qua tutto ok.
Poi il prof dice:
Pongo $S(m) = T(2^m)$ e ottengo $S(m) = 2S(m/2) + m$


Non capisco... io avrei fatto così:

Prendo $T(2^m) = 2T(2^(m/2)) + log (2^m)$, lo riscrivo come $2T(2^m * 2^(-2))) + log (2^m)$
Pongo $S(m) = T(2^m)$ e ottengo $S(m) = 2S(m/2^2) + m$

Dove sta il mio errore?

Risposte
apatriarca
\[ 2^{m/2} \neq 2^m \, 2^{-2} = 2^{m - 2}.. \]

BoG3
Ai ai ai ai aiiii

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.