Considere essa versão do Teorema Mestre:
Seja \(a\ge 1\) e \(b>1\) constantes, \(f(n)\) uma função e \(T(n)\) definida usando a recorrência \[T(n)=a T(n/b) + f(n)\]
onde \(n/b\) significa \(floor {(n/b)}\) ou \(ceil {(n/b)}\).
Então \(T(n)\) tem os seguintes limitantes:
Se \(f(n)=O(n^{\log_{b} a-\epsilon})\) para algum \(\epsilon>0\), então \(T(n)=\Theta(n^{\log_{b} a})\).
Se \(f(n)=\Theta(n^{\log_{b} a})\) para algum \(\epsilon>0\), então \(T(n)=\Theta(n^{\log_{b} a}log_b n)\).
Se \(f(n)=\Omega(n^{\log_{b} a+\epsilon})\) para algum \(\epsilon>0\) e se \(af(n/b)\le c
f(n)\) para algum \(c<1\), então \(T(n)=\Theta(f(n))\).</p>
Note que esses problemas são uma aplicação direta do Teorema Mestre:
1) A primeira relação de recorrência cai no caso 1. Logo, \(T(n)=\Theta(n^2)\).
2) A segunda relação de recorrência cai no caso 2. Logo, \(T(n)=\Theta(n^2 \log n)\).
3) A terceira relação de recorrência cai no caso 3. Logo, \(T(n)=\Theta(n^3)\).