Matematyka.pl

Mam do rozwiązania następujące równanie rekurencyjne:
\(\displaystyle{ T(1) = 0}\)
\(\displaystyle{ T(n) = 2T(n/2) + \Theta(n^2)}\)

I podchodzę do tego tak
\(\displaystyle{ T(n)=\sum_{n=0}^{{\log_2n}}2^i \Theta\left(\frac{n^2}{2^{2i}}\right)}\)
Nie jestem przekonany o swoim postępowaniu, czy dobrze walczę z tymi równaniami asymptotycznymi, dlatego proszę o sprawdzenie i poprawienie w razie czego.
\(\displaystyle{ \sum_{n=0}^{{\log_2n}}2^i \Theta\left(\frac{n^2}{2^{2i}}\right)=n^2\sum_{n=0}^{{\log_2n}} \Theta\left(\frac{2^i}{2^{2i}}\right)=n^2\sum_{n=0}^{{\log_2n}} \Theta\left(\frac{1}{2^{i}}\right)=n^2\cdot O(1) = \Theta(n^2)}\)

też mi wyszła złożoność kwadratowa(taka wychodzi też z trzeciego przypadku twierdzenia o rek. uniwersalnej):

\(\displaystyle{ \frac{T(n)}{n} = \frac{T( \frac{n}{2} )}{ \frac{n}{2} } + \Theta(n)}\)

dla \(\displaystyle{ n=2^m}\) dostajemy:

\(\displaystyle{ \frac{T(2^m)}{2^m} = \frac{T(2^{m-1})}{2^{m-1}} + \Theta(2^m) =}\)

\(\displaystyle{ = \frac{T(2^{m-2})}{2^{m-2}} + \Theta(2^m + 2^{m-1}) =}\)

\(\displaystyle{ = 0 + \Theta(1 + 2 + \ldots 2^m + 2^{m-1}) = \Theta(2^m)}\)

czyli \(\displaystyle{ T(2^m) = 2^m \cdot \Theta(2^m)}\)

\(\displaystyle{ T(n) = n \cdot \Theta(n) = \Theta(n^2)}\)