Mestre Teorema: T(n) = 2T (n/2) + n/log n = ? Eu pensei que a resposta seria Θ (nlogn), mas a solução diz que o Teorema Mestre não se aplica.

O teorema mestre aplica-se apenas a recorrências da forma [matemática]T(n) = a\cdot T(n/b) + f(n)[/math], onde a função [matemática]f(n)[/math] é um polinômio. Sua função [matemática]n/\log n[/math] não é um polinômio, então o teorema mestre não se aplica.

Mas eu não me preocupo em lembrar o teorema mestre; é muito mais fácil usar árvores de recorrência diretamente.

Para simplificar a análise, e porque não importa, vou assumir que "[matemática]\log n[/math]" significa "[matemática]\log_2 n[/math]". (Toda vez que eu escrevo "porque não importa", a razão porque não importa é que minhas escolhas só afetam a constante escondida pela notação final [matemática]\Theta()[/math].)

A árvore de recorrência para [matemática]T(n)[/math] é uma árvore binária, cuja raiz tem valor [matemática]n/\log n[/math], e cujos dois filhos são árvores de recorrência de [matemática]T(n/2)[/math].

A árvore de recorrência para [matemática]T(n/2)[/math] é uma árvore binária, cuja raiz tem valor [matemática](n/2)/\log (n/2)[/math], e cujos dois filhos são árvores de recorrência de [matemática]T(n/4)[/math]. Assim, o valor total de todos os 2 nós no nível 1 é [matemática]2\cdot(n/2)/\log(n/2) = n / ((\log n) - 1)[/math].

A árvore de recorrência para [matemática]T(n/4)[/math] é uma árvore binária, cuja raiz tem valor [matemática](n/4)/\log(n/4)[/math], e cujos dois filhos são árvores de recorrência de [matemática]T(n/8)[/math]. Assim, o valor total de todos os 4 nós no nível 1 é [matemática]4\cdot(n/4)/\log(n/4) = n / ((\log n) - 2)[/math].

Mais geralmente, existem exatamente [matemática]2^L[/math] nós no nível [matemática]L[/math], cada um dos quais é a raiz de uma árvore de recursividade para [matemática]T(n/2^L)[/math]. (Esta observação é fácil de provar por indução em L se for necessário.) Assim, o valor total de todos os nós no nível [matemática]L[/math] é [matemática]2^L\cdot(n/2^L)/\log(n/2^L) = n/((\log n) - L)[/math].

O fundo da árvore de recursões quando [matemática]n/2^L[/math] é menor que a sua constante favorita. Porque não importa, minha constante favorita é 1, o que significa que as folhas estão no nível [matemática]\log_2 n[/math]. Porque não importa, vou assumir que [matemática]T(1) = 0[/math].

Então o valor total de todos os nós na árvore de recorrência é

[matemática]}begin{align}. T(n) &= \sum_{L=0}^{\log_2 n - 1} \Frac{n}{n}{log_2 n - L} &= n {cdot }sum_{L=0}^{\i1}^log_2 n - 1} \Frac{1}{1}log_2 n - L} \\ n {i=1}^^log_2 n^sum_ \Frac{1}{i} & [i = {log_2 n - L] &= n {cdot H_{{\i} n} \a1}end{alinhamento}[/math]

p>onde [matemática]H_k := \a1}^k 1/i[/math] é o [matemática]k[/math]o número harmônico. Porque [matemática]H_k = \Theta(\log k)[/math], temos imediatamente [matemática]T(n) = \Theta(n\log n)[/math].