Método iterativo de recorrência

---

Recorrência dada:

$$T(n)=2T\left(\frac{n}{2}\right)+n$$

O que isso significa é que o tempo para resolver o problema de tamanho $n$ (ou seja, $T(n)$) é igual a duas vezes o tempo para resolver um problema de tamanho $\frac{n}{2}$, mais um tempo linear $n$.

Agora, vamos expandir a recorrência para enxergar o padrão. A ideia é substituir recursivamente os termos que envolvem $T$.

Passo 1: Primeira expansão

Nós temos $T(n)=2T\left(\frac{n}{2}\right)+n$.

Agora, substituímos o $T\left(\frac{n}{2}\right)$ pela sua definição, que é:

$$T\left(\frac{n}{2}\right)=2T\left(\frac{n}{4}\right)+\frac{n}{2}$$

Substituindo isso na fórmula original:

$$T(n)=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n$$

Passo 2: Simplificação

Agora, vamos simplificar o que obtivemos:

$$T(n)=2\cdot 2T\left(\frac{n}{4}\right)+2\cdot \frac{n}{2}+n$$

Isso se torna:

$$T(n)=4T\left(\frac{n}{4}\right)+n+n=4T\left(\frac{n}{4}\right)+2n$$

Passo 3: Segunda expansão

Agora, expandimos novamente, substituindo $T\left(\frac{n}{4}\right)$ por sua definição, que seria:

$$T\left(\frac{n}{4}\right)=2T\left(\frac{n}{8}\right)+\frac{n}{4}$$

Substituímos isso:

$$T(n)=4\left(2T\left(\frac{n}{8}\right)+\frac{n}{4}\right)+2n$$

Passo 4: Simplificação

Novamente, simplificamos:

$$T(n)=4\cdot 2T\left(\frac{n}{8}\right)+4\cdot \frac{n}{4}+2n$$ $$T(n)=8T\left(\frac{n}{8}\right)+n+2n=8T\left(\frac{n}{8}\right)+3n$$

Padrão Geral

A cada expansão, o coeficiente multiplicador de $T$ aumenta como potências de 2, e o termo linear também cresce de forma acumulativa.

De forma geral, após $k$ expansões, teremos algo como:

$$T(n)=2^{k}T\left(\frac{n}{2^k}\right)+kn$$

Condição de parada

Agora, precisamos parar quando o argumento de $T$, ou seja, $\frac{n}{2^k}$, for igual a 1. Isso acontece quando $k={\log }_2(n)$, pois:

$$\frac{n}{2^{{\log }_2(n)}}=1$$

Quando isso acontecer, sabemos que $T(1)$ é uma constante (vamos chamar de $T(1)=c$).

Substituindo na fórmula geral:

$$T(n)=2^{{\log }_2(n)}T(1)+n{\log }_2(n)$$

Como $2^{{\log }_2(n)}=n$, temos:

$$T(n)=n\cdot c+n{\log }_2(n)$$

Portanto, ignorando a constante $c$, temos:

$$T(n)=O(n\log n)$$

Referências

---

Aula 2 - Análise de algoritmos