Při určování časové složitosti algoritmu založeného na metodě Rozděl a panuj se typicky dostaneme k rekurenci, kterou potřebujeme vyřešit. Abychom ji nemuseli zdlouhavě rozepisovat a přemýšlet, jak ji vyřešit, naučíme se následující univerzální metodu.

Věta (Master theorem):
Nechť $T:\NN \to \NN$ je funkce splňující $$T(n) = a T(\lceil n/b \rceil) + \OO(n^d)$$ pro nějaké konstanty $a>0$, $b>0$ a $d \geq 0$. Potom $$T(n)= \left\{
\begin{array}{l l}
\OO(n^d) & \quad \mbox{pokud $d>\log_b a$}\\
\OO(n^d \log n) & \quad \mbox{pokud $d=\log_b a$}\\
\OO(n^{\log_b a}) & \quad \mbox{pokud $d<\log_b a$}\\ \end{array} \right.$$ [/theorem] [proof] Pro jednoduchost předpokládejme, že $n$ je mocnina $b$. Díky tomu je $\lceil n/b \rceil = n/b$. Velikost podproblémů se při každém rekurzivním zanoření zmenší $b$ krát. Proto se po nejvýše $\log_b n$ zanořeních zmenší až na konstantu (základní případ). Z toho dostáváme, že výška stromu rekurze je nejvýše $\log_b n$. [svg src="master_thm1.svg" float="center"] Při každém rekurzivním zavolání se rozvětvíme na $a$ podproblémů. Proto bude na $k$-té hladině stromu rekurze $a^k$ podproblémů, každý o velikosti $n/b^k$. Všechna práce prováděná na $k$-té hladině trvá $$ a^k \cdot \OO(\left(\frac{n}{b^k}\right)^d ) = \OO( n^d ) \cdot\left( \frac{a}{b^d}\right)^k .$$ [noindent]Časy strávené v hladinách $0$ až $\log_b n$ tvoří geometrickou posloupnost s kvocientem $a/b^d$. Celková časová složitost $T(n) = \OO(n^d)\cdot \sum_{k=0}^{\log_b n} \left(\frac{a}{b^d}\right)^k$. Podle hodnoty kvocientu nastanou následující tři případy:
  • $a/b^d<1$. Posloupnost je klesající. Největší je první člen $\OO(n^d)$. Součet prvních $\log_b n$ členů geometrické posloupnosti je nejvýše kvocient-krát větší než první člen. Proto $T(n)=\OO(n^d)$.
  • $a/b^d=1$. Všechny členy posloupnosti mají stejnou velikost a to $\OO(n^d)$. Proto $T(n)=\OO(n^d)\cdot \log_b n$.
  • $a/b^d>1$. Posloupnost je rostoucí. Součet prvních $\log_b n$ členů geometrické posloupnosti je nejvýše kvocient-krát větší než poslední a největší člen. Jeho hodnota je $\OO(n^d \left({a}/{b^d}\right)^{\log_b n}) $. $$n^d \left(\frac{a}{b^d}\right)^{\log_b n}= n^d \left(\frac{a^{\log_b n}}{(b^{\log_b n})^d}\right)
    = a^{\log_b n}=a^{(\log_a n)(\log_b a)}=n^{\log_b a}.$$ Proto $T(n)=\OO(n^{log_b a})$.

Tyto případy přesně odpovídají rozdělení případů z věty.

Zbývá ukázat, že věta platí i pro $n$, které není mocninou $b$. Už víme, že věta platí pro $n$, která jsou mocninou $b$. Toho využijeme. Nechť $n_+$ je nejbližší mocnina $b$ větší než $n$. Podívejme se na první případ, kdy má řešení rekurence tvar $T(n)=\OO(n^d)$. Ostaní případy si odůvodníte analogicky.

Funkce $T(n)$ je rostoucí a proto $T(n) < T(n_+)$. Z nerovnosti $n_+ < bn$ plyne, že $\OO(n_+^d)=\OO((bn)^d)=\OO(n^d)$. Poskládáním nerovností dostaneme $T(n) < T(n_+) = \OO(n_+^d)=\OO(n^d)$. Proto $T(n)=\OO(n^d)$.[/proof] Jak se dá Master Theorem použít v algoritmech z předchozích sekcí knihy, u kterých už jsme časovou složitost spočítali jinak? Časová složitost binárního vyhledávání (vyhledávání půlením intervalu) je určena rekurencí $T(n)=T(n/2)+\OO(1)$. Pro její vyřešení použijeme Master Theorem s konstantami $a=1$, $b=2$, $d=0$ a dostaneme $T(n)=\OO(\log n)$. Časová složitost mergesortu je určena rekurencí $T(n)=2T(n/2)+\OO(n)$. Pro její vyřešení použijeme Master Theorem s konstantami $a=2$, $b=2$, $d=1$ a dostaneme $T(n)=\OO(n\log n)$. [bigskip] [example]Vyřešte rekurenci $T(n)=2T(\sqrt n)+\log n$. Tato rekurence vypadá jako ošklivá čarodějnice, ale můžeme z ní udělat Popelku, když vhodně převlékneme proměnné. Nejprve použijeme substituci proměnné $m=\log n$ a dostaneme $T(2^m)=2T(2^{m/2})+m$. Pak použijeme substituci funkce $S(m)=T(2^m)$ a dostaneme $S(m)=2S(m/2)+m$. Tuhle krásku už umíme vyřešit například pomocí Master Theoremu. $S(m)=\OO(m\log m)$. Změnou $S(m)$ zpět na $T(n)$ dostaneme $T(n)=T(2^m)=S(m)=\OO(\log n \log\log n)$. (Všechny substituce jsou korektní, protože jsme použili rostoucí funkce.) [/example]