Ricorrenza lineare - non capisco un passaggio
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:
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?
$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
\[ 2^{m/2} \neq 2^m \, 2^{-2} = 2^{m - 2}.. \]
Ai ai ai ai aiiii