[Teoria złożoności] Rekurencja uniwersalna

[KotDrewniany1997]

Witam, nie rozumiem rekurencji uniwersalnej.

Zad.: Korzystając z Twierdzenia o Rekurencji Uniwersalnej, wyznacz asymptotycznie dokładne oszacowania poniższych rekurencji, a następnie porównaj rozwiązania otrzymane w punktach (a) i (b).

(a) \(\displaystyle{ T \left( n \right) = 2T \left( \frac{n}{4} \right) + \frac{n^{2}}{3}}\)

\(\displaystyle{ k = \frac{1}{2}}\)

\(\displaystyle{ f \left( n \right)}\) jest asymptotycznie szybsze od \(\displaystyle{ n^{1/2}}\) dlatego korzystam z oszacowania
jeżeli \(\displaystyle{ \bigvee_{ \epsilon >0}f \left( n \right) =O \left( n^{\log _ba- \epsilon} \right)}\), to \(\displaystyle{ T \left( n \right) = \Theta \left( n^{\log _ba} \right)}\).

? \(\displaystyle{ f \left( n \right) = O\left( n^{\frac{1}{2}-\epsilon} \right) \right)}\)

\(\displaystyle{ \frac{n^{2}}{3} \le c \cdot n^{\frac{1}{2}-\epsilon}}\)

podstawiam \(\displaystyle{ \epsilon = \frac{1}{2}}\)

\(\displaystyle{ \frac{n^{2}}{3} \le c}\)

Tak, dla \(\displaystyle{ \epsilon = \frac{1}{2}, n = 1, c \ge \frac{1}{3}}\)

Czyli odpowiedź to \(\displaystyle{ T \left( n \right) = \theta \left( n^{\frac{1}{2}} \right)}\)

(b) \(\displaystyle{ T \left( n \right) = 3T \left( \frac{n}{9} \right) + \sqrt{n} + 2n^{\frac{1}{3}}}\)

\(\displaystyle{ k = \frac{1}{2}}\)

\(\displaystyle{ f \left( n \right)}\) asymptotycznie szybsze od \(\displaystyle{ n^{\frac{1}{2}}}\) więc korzystam z tego samego oszacowania

\(\displaystyle{ n^{\frac{1}{2}} + 2n^{\frac{1}{3}} \le c \cdot n^{\frac{1}{2}-\epsilon}}\)

podstawiam za \(\displaystyle{ \epsilon = 1}\)

\(\displaystyle{ n^{\frac{1}{2}} + 2n^{\frac{1}{3}} \le c \cdot n^{-\frac{1}{2}}}\)

\(\displaystyle{ n^{\frac{1}{2}} + 2n^{\frac{1}{3}} \le c \cdot \frac{1}{n^{\frac{1}{2}}} \ \ \ | : \frac{1}{n^{\frac{1}{2}}}}\)

\(\displaystyle{ n + 2n^{\frac{1}{3}} \cdot n{1}{2} \le c}\)

Tak, dla \(\displaystyle{ \epsilon = 1, n = 1, c \ge 3}\)

Czyli \(\displaystyle{ T \left( n \right) = \theta \left( n^{\frac{1}{2}} \right)}\)

Czy jest to poprawne rozumienie? Czy jeżeli miałabym f(n) asymptotycznie wolniejsze od \(\displaystyle{ n^{k}}\) powinnam użyć \(\displaystyle{ \bigvee_{ \epsilon >0}f \left( n \right) = \Omega \left( n^{\log _ba+ \epsilon} \right)}\) oraz \(\displaystyle{ \bigvee _{c_1<1} \bigvee _{n_0 \in N} \bigwedge _{n \ge n_0} af \left( \frac{n}{b} \right) \le cf \left( n \right)}\) , to \(\displaystyle{ T \left( n \right) = \Theta \left( f \left( n \right) \right)}\). Jeżeli byłoby takie samo, to \(\displaystyle{ f \left( n \right) = \Theta \left( n^{\log _ba} \right)}\), to \(\displaystyle{ T \left( n \right) = \Theta \left( n^{\log _ba}lgn \right)}\). W poleceniu zadania jest: "a następnie porównaj rozwiązania otrzymane w punktach (a) i (b)". Czy ktoś rozumie o co chodzi? Jak je porównać?

Proszę o odpowiedź. Każda pomoc i wyjaśnienia są na wagę złota.

[arek1357]

A nie lepiej zamiast tych pierdół napisać wzór tej rekurencji bardziej przejrzyście i jasno, np. będzie...
przyjąć np:

\(\displaystyle{ T(1)=1}\)

\(\displaystyle{ T(n)= \frac{13}{21} \sqrt{n}+ \frac{8}{21}n^2}\)

I po krzyku...