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>

 

Tak zdefiniowane funkcje ''T'' stanowią pewien schemat działania algorytmów typu "[[dziel i zwyciężaj]]" - problem o rozmiarze <math>\! n</math> dzielony jest na <math>\! a</math> podproblemów, każdy wielkości <math>\! \frac{n}{b}</math>, funkcja <math>\! f</math> przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.