Escrito por
Mateus Almeida
em
Teorema Mestre
1º Caso
Se \(f(n) = O(n^{log_ba-\varepsilon}) | \varepsilon > 0 \therefore T(n) = \Theta(n^{log_ba})\)
a: número de chamadas recursivas
b: número de partes em que está sendo dividida a entrada
c: constante
\[T(n) = 9T(n/3)+n
\\
a = 9;b = 3;f(n) = n
\\
f(n) = O(n^{lg_39-\varepsilon})
\\=O(n^{2-1}) = O(n) | \varepsilon = 1
\\=\therefore T(n)=\Theta{(n^{log_ba})} = \Theta({n^{2}})\]
2º Caso
Se \(f(n) = \Theta(n^{log_ba}) \therefore T(n) = \Theta(n^{log_ba} \cdot log_n)\)
\[T(n) = T(2n/3)+1
\\
a = 1;b = 3/2;f(n) = 1
\\
f(n) = O(n^{lg_\frac{3}{2}1})
\\=\Theta(n^{0}) = \Theta(1)
\\=\therefore T(n)=\Theta(n^{lg_\frac{3}{2}1} \cdot log_2n)\]
3º Caso
Se \(f(n) = \Omega(n^{log_ba+\varepsilon}) | \varepsilon > 0\) e se \(a \cdot f(n/b) \leq c \cdot f(n)\) para alguma constante c < 1 e para um n suficientemente grande \(\therefore T(n) = \Theta(f(n)\))
\[T(n) = 3T(n/4)+n lg n
\\
a = 3;b = 4;f(n) = n lg n
\\
f(n) = \Omega(n^{lg_4 3 + \varepsilon})
\\=\Omega(n^{0.8...+0.2}) = \Omega(n^{1}) | \varepsilon = 0.2
\\f(n) = \Omega(n)?
\\\Rightarrow a \cdot f(n/b) \leq c \cdot f(n)
\\\Rightarrow 3\left ( (n lg n)/b \right ) \leq c \cdot f(n)
\\\Rightarrow 3n/4 \cdot log_2(n/4) \leq c \cdot f(n)
\\\Rightarrow 3n/4 \cdot log_2(n/4) \leq 3/4 \cdot n lg n | c = 3/4
\\\therefore T(n) = \Theta(n lg n)\]