Metodo dell'esperto

[takkkeo]

Non riesco a risolvere il seguente problema:

Data la seguente ricorrenza:
T( n ) = 0 se n=2
T( n ) = T(sqrt( n ))+1 se n>2

verificare che la soluzione è T( n ) = lg lg n

Credo che sia da risolvere con il metodo dell'esperto(http://it.wikipedia.org/wiki/Metodo_dell%27esperto) ma proprio non riesco a capire come è lo svolgimento....qualcuno riesce ad aiutarmi?

[hamming_burst]

Ciao,
prova a dare un'occhiata qui (pag. 2). Spiego cosa comporta l'utilizzo del Master in queste ricorrenze con costo della funzione libera costante.

Se avrai dubbi dopo aver letto, chiedi pure.

[vict85]

Il metodo dell'esperto prevede che \(\displaystyle b \) sia costante. Quindi non può essere usato direttamente. Per farlo è necessario un cambio di variabili.

Dimentica che tu stai lavorando con interi. Se tu ora hai un cambio di variabili \(\displaystyle m = f(n) \) invertibile e che mantiene l'ordine \(\displaystyle s > t \leftrightarrow f(s) > f(t) \) allora risulterà \(\displaystyle T(m) = \Theta\bigl(g(m)\bigr) \leftrightarrow T(n) = \Theta\Bigl(g\bigl(f(n)\bigr)\Bigr) \).

Ora che lo sai prova a trovare un cambio di variabile adeguato...