Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie.
Twierdzenie o rekurencji uniwersalnej Niech będą stałymi niezależnymi od i niech będzie funkcją asymptotycznie nieujemną, czyli przyjmującą wartości nieujemne dla wystarczająco dużych . Jeżeli funkcja dla jest zdefiniowana następująco:
to: <li>jeżeli istnieje stała dla której , to <li>jeżeli istnieje stała dla której to
<li> jeżeli istnieje stała dla której i jeżeli dodatkowo spełniony jest warunek regularności, dla pewnej stałej dla dostatecznie dużych to
Tak zdefiniowane funkcje stanowią pewien schemat działania algorytmów typu „dziel i zwyciężaj” – problem o rozmiarze dzielony jest na podproblemów, każdy wielkości funkcja przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.
Intuicyjna interpretacja Przypadki 1 i 3 rekurencji uniwersalnej polegają na rozstrzyganiu, która z funkcji czy rośnie wielomianowo szybciej, i funkcja ta stanowi wówczas dokładne oszacowanie rekurencji . W przypadku 2 funkcje te rosną w takim samym tempie wielomianowym, jednak z możliwym czynnikiem polilogarytmicznym.