Rekurencja uniwersalna - funkcje

[krniasty]

Skorzystaj z rekurencji uniwersalnej i podaj dokładne asymptotyczne oszacowane dla poniższych rekurencji. We wszystkich przypadkach zakładamy, że \(T(1) = \Theta(1)\)

Korzystam z danego twierdzenia:

Dla funkcji T(n) zadanej przez:
\(T(n)= \left\{\begin{array} {ll} \Theta(1), & \textrm{dla}\quad n\in \{0,1\} \\ a\cdot T( \lfloor\frac{n}{b}\rfloor )+f(n), & \textrm{dla}\quad n>1 \end{array} \right.\)

Zachodzi:
a) Jeśli \(f(n)=O(n^{\log_b{a}-})\) dla pewnego \(> 0\), to \(T(n)=\Theta(n^{\log_b{a}})\)
b) Jeśli \(f(n)=\Theta(n^{\log_b{a}})\), to \(T(n)=\Theta(n^{\log_b{a}}\lg{n})\)
c) Jeśli \(f(n)=\Omega(n^{\log_b{a}+})\) dla pewnego \(> 0\) oraz \(a f(\frac{n}{b})\leq c f(n)\) dla pewnego \(c < 1\) i prawie wszystkich n, to \(T(n)=\Theta(f(n))\)

a) \(T(n) = 2T (\frac{n}{2}) + 5\)
\(a = 2 \\ b = 2 \\ f(n) = 5\)
\(n^{log_2 2} = n^1 = 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 (\frac{n}{2}) + n^2\)
\(a = 3 \\ b = 2 \\ f(n) = n^2\)
\(n^{log_3 2} = O(n^{0.631}) \)
Tutaj taka sama sytuacja jak powyżej

c) \(T(n) = T (\frac{n}{2}) + 2n\)
\(a = 1 \\ b = 2 \\ f(n) = 2n\)
\(n^{log_2 1} = n^0 = 1\)
\( T(1) = \Theta(1) \)

d)\(T(n) = 4T (\frac{n}{2}) + n\)
\(a = 4 \\ b = 2 \\ f(n) = n\)
\(n^{log_2 4} = n^2\)
\( n^2 > n \) - czyli znowu warunek c)

Z góry dziękuję za pomoc i uwagi / poprawki jeśli coś jest nie tak, jak należy.