Rekurzivne enačbe tipa "deli in vladaj"

Imamo funkciji:

Definicija:

Osnovni izrek

Naj bosta konstanti in funkcija . Funkcija f naj zadošča rekurzivni zvezi: , kjer se označuje z ali (tisti, ki je manjši od n)

Potem velja:

1. če je , ε je poljubna pozitivna konstanta, potem je .
2. če je , potem je .
3. če je in velja za neko konstanto c < 1 in za vse dovolj velike n-je, potem je T(n) = Θ(f(n)).

Primer naloge

Naj bo čas izvajanja algoritma A opisan z . Konkurenčni algoritem B ima časovno zahtevnost . Kakšen je največji k, da je algoritem B asimptotično hitrejši od A.