Resolvendo usando o teorema do mestre

Introduction to Algorithms , 3rd edition (p.95) tem um exemplo de como resolver a recorrência

aplicando o Teorema Mestre.

Estou muito confuso com a forma como é feito. Então, primeiro passo é comparar com .$a=3, b=4, f(n) = n\cdot \log(n)$
$n^{\log_b a} = n^{\log_4 3}= O(n^{0.793})$$f(n)$

Não tenho idéia de como eles compararam isso. O livro explica:

$f(n) = \Omega (n^{\log_4 3+\epsilon })$ , onde , o caso 3 se aplica se pudermos mostrar que a condição de regularidade é válida para$\epsilon \approx 0.2$$f(n).$

Seguido por:

Para n suficientemente grande, temos o seguinte:$af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$

De onde veio ?$3\left(\frac{n}{4}\right)$

Se nossa recorrência assumir a forma , para usar o "terceiro caso" do método Master, devemos ter o seguinte:$T(n) = aT(n/b) + f(n)$

$f(n) = \Omega(n^{\log_b a + \epsilon})$ para alguns e se para alguma constante e todos suficientemente grandes , então$\epsilon > 0$$a f(n/b) \leq c f(n)$$c < 1$$n$$T(n) = \Theta(f(n))$

Nossa recorrência é definida como

Por definição, temos .$a = 3, b = 4, f(n) = n \log n$

Agora precisamos mostrar que é polinomialmente maior que . Essa é a parte " " acima. Definir consegue isso. A razão é que e .$f(n)$$n^{\log_b a}$$f(n) = \Omega(n^{\log_b a + \epsilon})$$\epsilon \approx 0.2$$\log_4 3 \approx 0.793$$f(n) = \Omega(n^{0.793 + \epsilon})$

Nos resta mostrar que satisfaz a condição de regularidade. Essa é a " para alguma parte constante e todas as partes suficientemente grandes ".$f(n)$$a f(n/b) \leq c f(n)$$c < 1$$n$

Simplesmente inserimos nossos valores de para obter:Tudo o que fizemos foi pegar o " " em e conectar " ".$a,b$

Para facilitar a visualização, deixe e observe que . Trocando com , temos onde .$k = n/4$$a f(k) = a k \log k$$k$$n/4$

Isso termina nossos requisitos necessários e temos que .$T(n) = \Theta(n \log n)$