76026 zdj2 (3)

Metoda rekurencji uniwersalnej

Niech a > 1. b > 1. T(n) zdefiniowane przez rekurencję

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

Tin) może być ograniczona asymptotycznie w następująco

1.    Jeśli f(n) = 0(n^logb“ ) dla pewnej stałej e 0. to T(n) = 0(n^u^^b<t)

2.    Jeśli f(n) = ®(w^logfc"). to Tin) =    Ig/?)

3.    Jeśli/(») = Q(/?^log*"^,ł;) dla pewnej stałej s 0 i jeśli <.//(/? h)<f(n) dla pewnej stałej c I i wszystkich dostatecznie dużych n. to

i    T{n) =©(/(//))

Wykład

Programowanie komputerów I

23

0—1