Nechť a ≥ 1 a b > 1 jsou reálné konstanty, f(n) kladná funkce jedné proměnné. Uvažujme rekurentní rovnici
t(n) = a·t(nb) + f(n),
kde n/b může znamenat ⌈n/b⌉ listů a ⌊n/b⌋ a tyto rozdíly zanedbáváme. Pak t(n) má následující asymptotické řešení:
- Pokud f(n) = O(nlogba−ε)pro nějakou konstantu ε > 0, pak t(n) = Θ(nlogba).
- Pokud f(n) = Θ(nlogba), pak t(n) = Θ(nlogbalogn).
- Pokud f(n) = Ω(nlogba+ε) pro nějakou konstantu ε >0 a pokud:
- af(n/b) ≤ d·f(n) pro nějakou konstantu d∈(0,1)a všechna n≥n0, pak t(n) = Θ(f(n)). (opak případu (1), f(n) je polynomiálně větší než logba.)
Tyto 3 případy nepokrývají všechny případy. Pokud je rozdíl mezi funkcemi menší než polynomiální, nelze tuto metodu použít!
Od iterační metody k mistrovské
t(n) = a·t(n/b) + f(n), = a·t(n/b) + a2·t(n/b2) = f(n) + a2·t(n/b2) + a3·t(n/b3) = k−1^∑_j=0 aj·f(n/bj) + ak·t(1) (pro 1≤k≤logbn) ... Záleží na tom, co je asymptoticky ”větší" nlogba nebo suma závislá na f(n)