- Calcule o tempo de um algoritmo cuja relação de recorrência é
.
Passo 1
O enunciado dá a recorrência
e pede o tempo assintótico. O conteúdo usado será expansão repetida até o caso base e contagem do número de níveis de recursão.
Passo 2
Definimos
e, em geral,
Por indução obtém-se
Em cada nível de recursão há custo
.
Passo 3
Para achar o número de níveis
até atingir o caso base constante, exigimos
Tomando logaritmo natural,
Passo 4
Cada um dos
níveis custa
, logo