Metoda rekurencji uniwersalnej Sebek: Metoda rekurencji uniwersalnej. Witam, proszę o WYTŁUMACZENIE mi jak szacować asymptotycznie dokładnie rekurencje.

	n
a) T(n) = 8T (		) + n2
	2

//wiem, że na początku szacuję przez n^{log₂ 8} logarytm = 3 Dalej nie wiem nawet w jaki sposób wybrać odpowiedni wzór (to chyba największa trudność dla mnie). Nie wiem kiedy wybieram ten z Ω, O, θ

Sebek:

Sebek: Wymyśliłem coś takiego: f(n) = n² n^{lof₂ 8} = n³ n² < n³, więc: punkt pierwszy twierdzenia o rekurencji uniwersalnej: T(n) = θ(n³) O to chodzi?

Sebek: Proszę o sprawdzenie oraz pomoc w rozwiązaniu tych, których nie umiem. Zadanie 1.

	n
T(n) = 16T(		) + n
	4

a = 16; b=4; f(n) = n n^{log₄ 16} = n² n² > n więc korzystam z punktu (1) twierdzenia o rekurencji uniwersalnej: T(n) = θ(n²) Zadanie 2.

	n
T(n) = 2T(		) + √n
	4

a = 2; b=4; f(n) = p(n) n^{log₄ 2} = n^1/2= √n √n = √n, więc korzystam z (2) punktu tw. o rekurencji uniwersalnej. t(n) = θ (√nlgn) Zadanie 3.

	n
T(n) = 2T(		) + √nn2
	4

a=2; b=4; f(n)=√nn² n{log₄ 2) = n^1/2 = √n √n < √nn^, więc korzystam z (3) punktu tw. o rekurencji uniwersalnej //nie umiem zastosować 3−wzoru Zadanie 4.

	n
T(n) = 64T(		) + n3√n
	4

a = 64; b = 4; f(n) = n² √n n^{log₄ 64} = n³ n³ < n³*√n, punkt(3) twierdzenia o rekurencji uniwersalnej //nie umiem zastosować Zadanie 5.

	n
T(n) = 64T(		) + n;
	4

a = 64; b=4; f(n) = n n^{log₄ 64} = n³ n³ > n więc używam (1) punktu tw. o rek. uni. T(n) = θ(n³) Zadanie 6.

	n
T(n) = 64T(		) + n3
	4

a = 64; b=4; f(n)=n³ n^{log₄ 64} = n³ n³ = n³, więc wzór (2) z tw. o rek. uniwers. T(n) = θ(n³ lgn)

Sebek:

Sebek:

Sebek: