- Qual a solução de relação de recorrência
?
Passo 1
O enunciado pede para resolver a relação de recorrência
para
da forma
. O conteúdo é solução de recorrência com variação de argumento por fator constante (doubling). Para resolver, vamos usar mudança de variável para um índice
.
Passo 2
Defina
e
Então, quando
passa para
, isto é, de
para
, a recorrência vira
Passo 3
Temos agora a nova recorrência
com condição inicial
. Para encontrar
, desdobramos a soma:
Passo 4
Unrolando de
a
,
Passo 5
Voltando à variável original, como
, obtemos
Em termos de ordem de grandeza, isso significa
.