Title: Mistrovská metoda
Description:
Import: [Asymptotická složitost]
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í:
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!