non sono molto sicuro che sia questa la sezione migliore per il mio posto. E' un problema di Algoritmi e strutture dati ma il problema che ho è di tipo algebrico.
Ho una domanda su una ricorrenza della quale devo trovare la complessita': $T(n) = 2T(n^(1/2))+log n$
Quotero' i passaggi suggeriti dal libro e sotto il quote faro' le mie domande.
sostituire $n = 2^m$ ed otteniamo $T(2^m) = 2T(2^(m/2))+log 2^m$
Ok, chiaro!
.Poniamo $S(m) = T(2^m)$ e otteniamo $S(m) = 2S(m/2)+m$
Ecco, qua non ho mica capito. Come ha sostituito e come ha semplificato?
Mi spiego meglio: Ho capito che ha preso la funzione $T$ che ha come parametro $2^m$ e ha detto: mi costruisco una funzione $S$ che prenda "solo l'esponente del paramento di $T$" (perdonate la spiegazione brutale che faccio) e quindi il mio $2^(m/2)$ diventa $m/2$.
Pero' non mi è per nulla chiaro come abbia fatto qul $log 2^m$ a diventare $m$.
Ehm, ora che rileggo cio' che ho scritto mi viene in mente una spiegazione banale ed ovvia: $log 2^m = m*log 2 = m*1$. giusto?
Vi spiego quello che avevo pensato prima io: se applico $S(m)$ a $log 2^m$ ottengo $log m$ che evidentemente era sbagliato. Potete dirmi perchè dato che io posso scrivere $log 2^m = log(2^m)$ il che è come dire $f(g(m))$ e dato che io applico la mia $S$ a $2^m$, l'avrei applicato a $log (2^m)$ ed avrei avuto $log m$. Dove ho toppato?
Grazie a tutti
