Rekurencja uniwersalna Marcin: Skorzystaj z rekurencji uniwersalnej i podaj dokładne asymptotyczne oszacowane dla poniższych rekurencji. We wszystkich przypadkach zakładamy, że T(1)=Θ(1) Korzystam z danego twierdzenia: Dla funkcji T(n) zadanej przez:

⎧	Θ(1), dla n ∊ {0, 1}
⎩	a*T(⌊ n b ⌋) + f(n), dla n>1

Zachodzi: a) Jeśli f(n)=O(n^log_ba−) dla pewnego >0, to T(n)=Θ(n^log_ba) b) Jeśli f(n)=Θ(n^log_ba), to T(n)=Θ(n^log_balg n) c) Jeśli f(n)=Ω(n^log_ba+) dla pewnego > 0 oraz af(ⁿ_b) ≤ cf(n) dla pewnego c < 1 i prawie wszystkich n, to T(n)=Θ(f(n)) a) T(n)=2T(ⁿ₂)+5 a = 2 b = 2 f(n) = 5 n^log₂2 = n¹ = n Czy ktoś może mnie dalej pokierować? Według mnie zachodzi tutaj warunek c) jednakże nie wiem jak to ruszyć b) T(n)=3T(ⁿ₂) + n² a = 3 b = 2 f(n) = n² n^log₃2 = O(n^0.631) Tutaj taka sama sytuacja jak powyżej c)T(n)=4T(ⁿ₂) + n a = 4 b = 2 f(n) = n n^log₂4 = n² n² > n − czyli znowu warunek c)

Adamm: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) a) Tutaj f(n) = Theta(n^log_ba−r) gdzie r = 1, więc T(n) = Theta(n) b) Tutaj f(n) = Theta(n^log_ba+r) gdzie r = 2−log₂3 > 0 Dodatkowo a•f(n/b) = 3/4 f(n) więc warunek zachodzi Stąd T(n) = Theta(n²) c) Tutaj f(n) = Theta(n^log_ba−r) gdzie r = 1, więc T(n) = Theta(n²)