ma wówczas rozwiązanie zbliżone do tego wspólnego tempa wzrostu.
„Dziury” rekurencji uniwersalnej Twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków dla rekurencji w powyższej postaci. Nie znajduje ono zastosowania gdy funkcji i nie da się porównać asymptotycznie, np. gdy dla dowolnie dużych , i dla innych dowolnie dużych , . W przypadkach 1 i 3 tempa wzrostu funkcji i muszą różnić się o czynnik wielomianowy. Dodatkowo w przypadku 3 oprócz dominacji asymptotycznej wymagana jest pewna „regularność” funkcji . Intuicyjnie, warunek regularności może nie być spełniony, jeśli funkcja ta rośnie zbyt wolno lokalnie, mimo wystarczającego globalnego tempa wzrostu.
Przykłady rekurencji nierozwiązywalnych metodą rekurencji uniwersalnej
nie jest stałą niezależną od .
Funkcja nie jest asymptotycznie nieujemna.
Zarówno jak i - nie da się więc asymptotycznie porównać i .
Nie jest zachowany wielomianowy wzrost między i .
Nie zachodzi warunek regularności:
Czynnik jest mniejszy od 1 dla każdego , ale wraz ze wzrostem zbliża się dowolnie do 1, dlatego nie istnieje stała taka że .
Kategoria:Rekurencja o rekurencji uniwersalnej Kategoria:Algorytmika