Método iterativo de recorrência §

---

Recorrência dada:

O que isso significa é que o tempo para resolver o problema de tamanho (ou seja, ) é igual a duas vezes o tempo para resolver um problema de tamanho , mais um tempo linear .

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

Passo 1: Primeira expansão §

Nós temos .

Agora, substituímos o pela sua definição, que é:

Substituindo isso na fórmula original:

Passo 2: Simplificação §

Agora, vamos simplificar o que obtivemos:

Isso se torna:

Passo 3: Segunda expansão §

Agora, expandimos novamente, substituindo por sua definição, que seria:

Substituímos isso:

Passo 4: Simplificação §

Novamente, simplificamos:

Padrão Geral §

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

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

Condição de parada §

Agora, precisamos parar quando o argumento de , ou seja, , for igual a 1. Isso acontece quando , pois:

Quando isso acontecer, sabemos que é uma constante (vamos chamar de ).

Substituindo na fórmula geral:

Como , temos:

Portanto, ignorando a constante , temos:

Referências §

---

Aula 2 - Análise de algoritmos