Esta instância específica pode ser resolvida facilmente desenhando como a função T (n) recursiva é calculada. Cada chamada para T (n) tem um custo de θ (n) mais duas vezes o custo de metade do tamanho do problema.
T(n) = ...
0: θ(n)
/ \
1: θ(n/2) θ(n/2)
/ \ / \
2: θ(n/4) θ(n/4) θ(n/4) θ(n/4)
/ \ ⋰⋱ ⋰⋱ ⋰⋱
3: θ(n/16) θ(n/16) ⋯ ⋯ ⋯ ⋯ ⋯ ⋯
⋰⋱ ⋰⋱
θ(1) θ(1) ⋯ ⋯
Cada nível tem duas vezes o número de termos do que o nível anterior. A árvore inteira é log 2 n níveis profundos. Então, qual é a soma de todos os nós nesta árvore? Podemos descrevê-lo como a soma
20·θ(n/20) + 21·θ(n/21) + 22·θ(n/22) + ⋯ + 2(log2 n)·θ(1)
= 20·θ(n/20) + 21·θ(n/21) + 22·θ(n/22) + ⋯ + n·θ(n/n)
= Σi = 0 ... log2n 2i·θ(n/2i)
= Σi = 0 ... log2n θ(n)
= log2(n) · θ(n)
= θ(n · log n)
(Nota: isso pressupõe que a · θ (b · n) = θ (a · b · n) é óbvia, o que tecnicamente eu teria que mostrar em uma prova rigorosa.)
No entanto, esses cálculos são impraticáveis no caso geral. Portanto, normalmente aplicamos o Teorema Mestre que nos dá a complexidade se o tempo de execução recursivo da forma T (n) = a · T (n / b) + f (n) corresponde a um padrão específico. Aqui a = 2, b = 2, f (n) = θ (n).
Com o Teorema Mestre, o caso corresponde onde c = log b a = 1 e f (n) = θ (n c · log k n) com k = 0. Isso nos diz que T (n) = θ (n c · log k + 1 n) = θ (n · log n). Assim, os dois caminhos chegam à mesma solução, mas o Teorema do Mestre é mais geral e também mais simples, porque só precisamos combinar a estrutura da nossa função recursiva para o tempo de execução com três padrões conhecidos.
Sua abordagem por indução não é satisfatória, porque você não está executando nenhuma etapa de indução . Geralmente, mostramos que a propriedade de indução deve ser mantida para n + 1 se ela for para n, portanto, é correto se ela também é válida para qualquer n conhecido (por exemplo, n = 1). Isto é excessivamente desconfortável de se fazer aqui, então seria melhor provar que uma propriedade vale para 2n se ela for para n. Deixarei isto como um exercício para o leitor;) mas gostaria de salientar que tal indução tecnicamente apenas provaria isso para potências de 2 em vez de todos n, e um argumento adicional seria necessário para generalizar isso.