Teorema master sulle ricorrenze

Siano a ≤ 1 e b ≤ 1 costanti e f(n) una funzione.

Sia T(n) il costo dell'esecuzione della ricorrenza.

Il Teorema Master delle ricorrenze dice che se il costo di esecuzione è nella forma:

T(n) = aT(n/b)+f(n)

allora, in base a quanto vale n^log_ba si presentano tre casi:

Vince la funzione

se asintoticamente f(n) è un tempo migliore di quello di n^log_ba allora il tempo di esecuzione è Θ(n^log_ba). Per esempio, 2T(n/2)+O(1).

Formalmente si dice f(n) = O(n^{log_ba - ε}), con ε > 0.

Sono pari

se asintoticamente i tempi si equivalgono (formalmente, f(n) = Θ(n^log_ba)), allora T(n) = Θ(n^log_ba log₂(n)). Per esempio, 2T(n/2)+O(n).

Vince la ricorrenza (ma...)

Se f(n) = Ω(n^{log_ba + ε}), con ε > 0, significa che f(n) ci mette più tempo - asintoticamente - di n^log_ba e quindi il tempo è Θ(f(n)). ma...

This is... the Master Theorem of the Recurrencies!