Algoritmi e equazioni di ricorrenza

[Valerioweb]

Buongiorno a tutti.
Ho problemi nel risolvere delle equazioni di ricorrenza....spero che qualcuno mi possa aiutare...o almeno darmi una dritta...

1) T(n) = 8T(n/3)+ (n^2)lgn

2) T(n) = 3T(n/6) + T(n/2) + n

Grazie mille a tutti!

[vict85]

Per il punto 1. Abbiamo che \(\displaystyle \log_3(8) \approx 1.89278926 < 2\), inoltre \(\displaystyle \frac89 n^2\log \frac{n}{3} = \frac89 n^2(\log n - \log 3) = c n^2\log n - g(n)\) dove \(\displaystyle g(n) \) è una funzione crescente positiva e \(\displaystyle c<1 \). A questo punto che punto del master theorem devi usare?

Il secondo ci devo pensare.

[hamming_burst]

per il 2. si può notare che, al primo passo di ricorsione, $3/6n + 1/2n = n$. I passi saranno di costo lineare limitati da...

[Valerioweb]

Ciao.
Grazie delle risposte!!!
Per il secondo avevo risolto con l'albero di ricorsione e mi viene O(nlgn) spero sia giusto....


Per il primo ho fatto anche li l'albero di ricorsione poi ho studiato le due serie che mi venivano e alla fine mi viene O(n^2lgn)
Con il tuo metodo intendi usare il terzo caso del teorema master???

Se la condizione fosse verificata quindi verrebbe O(f(n)) quindi con l'albero sarei arrivato alla giusta conclusione??

[hamming_burst]

"Valerioweb":
Per il secondo avevo risolto con l'albero di ricorsione e mi viene O(nlgn) spero sia giusto....

ok corretto.