Title: Mistrovská metoda

Description:

Import: [Asymptotická složitost]

Alias:

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!

Od iterační metody k mistrovské