Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami

* Jeżeli <math>\! f(n) = O(n^{\log_ba-\epsilon})</math> dla pewnej stałej <math>\! \epsilon > 0</math>, to <math>\! T(n) = \Theta (n^{\log_ba})</math>

* Jeżeli <math>\! f(n) = \Theta(n^{\log_ba})</math>, to <math>\! T(n) = \Theta (n^{\log_ba}\cdot \log\ n)</math>

* Jeżeli <math>\! f(n) = \Omega(n^{\log_ba+\epsilon})</math> dla pewnej stałej ε > 0 i jeżeli <math>\! a\cdot f(\frac{n}{b})\leqslant c\cdot f(n)</math> dla pewnej stałej <math>\! c \in (0,1)</math>, dla dostatecznie dużych ''n'', to <math>\! T(n)=\Theta(f(n))</math>

Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji <math>\! n^{\log_ba}</math> i ''f'' jest "większa". Gdy znana jest odpowiedź na to pytanie, automatycznie znane jest asymptotyczne ograniczenie danej rekursji - jest nią owa "większa funkcja".

Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji "typu" <math>\! T(\frac{n}{b}) + f(n)</math> - pomiędzy przypadkami twierdzenia istnieją "dziury". W pierwszym przypadku funkcja ''f'' musi być '''wielomianowo''' mniejsza od <math>\! n^{\log_ba}</math>. W trzecim przypadku oprócz '''wielomianowej''' większości wymagana jest pewna "regularność", "gładkość" funkcji. Jeżeli funkcja ''f'' należy do którejś z tych funkcji dla których nie ma "wielomianowej różnicy", to twierdzenie o rekursji uniwersalnej nie pozwala znaleźć asymptotycznego oszacowania rekursji.

: <math>\! T(n)\ =\ \Theta (n^{\log_ba})\ +\ \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math> (*)

** Koszt każdego liścia wynosi <math>\! T(1)\ =\ \Theta (1)</math>, a ponieważ <math>\! \frac{n}{b^{\log_bn}}\ =\ 1</math> to każdy liść znajduje się na głębokości <math>\! \log_bn</math>. Drzewo rekursji posiada <math>\! a^{\log_bn}\ =\ n^{\log_ba}</math> liści.

Sumując koszty wszystkich poziomów drzewa otrzymamy równanie (*), ponieważ koszt wszystkich "poziomów" węzłów właściwych (tj. niebędących liśćmi) wynosi <math> \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math> a koszt liści to <math>\! \Theta (n^{\log_ba})</math>

** Jeżeli <math>\! f(n) = O(n^{\log_ba-\epsilon})</math> dla pewnej stałej <math>\! \epsilon > 0</math>, to <math>\! g(n) = \Theta (n^{\log_ba})</math>

** Jeżeli <math>\! f(n) = \Theta(n^{\log_ba})</math>, to <math>\! g(n) = \Theta (n^{\log_ba}\cdot \lg\ n)</math>

** Jeżeli <math>\! f(n) = \Omega(n^{\log_ba+\epsilon})</math> dla pewnej stałej ε > 0 i jeżeli <math>\! a\cdot f(\frac{n}{b})\leqslant c\cdot f(n)</math> dla pewnej stałej <math>\! c \in (0,1)</math>, dla dostatecznie dużych ''n'', to <math>\! g(n)=\Theta(f(n))</math>

* <math>\! T(n)\ =\ \Theta (n^{\log_ba})\ +\ O(n^{\log_ba})\ =\ \Theta(n^{\log_ba})</math>

* <math>\! T(n) = \Theta (n^{\log_ba}) + \Theta(n^{\log_ba}\cdot \ln\ n) = \Theta(n^{\log_ba}\cdot \ln\ n)</math>

* <math>\! T(n) = \Theta (n^{\log_ba}) + \Theta(f(n)) = \Theta(f(n))</math>, ponieważ <math>\! f(n) = \Omega (n^{\log_ba + \epsilon})</math>