apatriarca ha scritto:Credo tu non abbia capito come funziona il teorema master. Ci sono tre casi da considerare e se la tua ricorrenza rispetta tutte le ipotesi di uno di questi casi, allora il teorema ti fornisce la soluzione. Ad una occhiata veloce credo che il secondo esercizio rientri in un caso diverso e che quindi il risultato sia anche diverso. Ma il teorema è solo una scorciatoia. È possibile seguire la strada che ho usato nel mio post precedente per arrivare agli stessi risultati.
In che caso rientra a questo punto?
Ad ogni modo ho provato a risolverlo con il metodo iterativo (perchè con gli alberi non mi trovo) e al caso finale cioè t(1), mi risulta è: \(\displaystyle n^2*T(1) + \sum_{k=0}^{log_4 n -1} 8^{k-1}*d((n/4^{k-1})\sqrt(n/4^{k-1})) \) che togliendo le varie n dalla sommatoria e semplificandola mi rimane sono sommatoria di 1^k che però non mi sembra abbia troppo senso.
Grazie.