- O limite
é uma boa solução para a relação
? Argumente usando o método iterativo.
Passo 1
O enunciado fornece a recorrência
e pede para verificar se
é um limite assintótico válido para
. Vamos usar o método iterativo (árvore de recursão) para estimar o custo total e ver que
.
Passo 2
Desenhemos a árvore de recursão. No nível 0 (raiz) temos custo
Esse nó gera dois filhos de tamanhos
e
.
Passo 3
No nível 1, os dois nós custam respectivamente
e
, totalizando
Em geral, em cada nível
a soma dos tamanhos dos subproblemas é sempre
pois a partição sempre adiciona até
.
Passo 4
Precisamos agora do número de níveis
até chegar a subproblemas de tamanho constante. A maior profundidade vem da cadeia que divide sempre pela mesma fração. Podemos olhar só para a subrecorrência maior
. Após
divisões temos tamanho
Passo 5
Cada um dos
níveis dá custo
. Ignorando o custo das folhas (constante), o total da árvore é
Em particular, isso mostra
.
Resposta
Sim. O método iterativo mostra que
logo
é de fato um limite assintótico válido para
.