Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual a complexidade computacional de um algoritmo recursivo que satisfaz a relação de recorrência \(T(n)=T(n/4)+T(n/2)+n^2\)?

0 votos
95 visitas

1 Resposta

0 votos
respondida Abr 8, 2016 por danielcajueiro (5,776 pontos)  

Note que podemos resolver esse problema facilmente usando uma árvore recursiva:

Raiz da árvore: \(n^2\)

Primeira geração: \(T(n/4)=(n/4)^2\) e \(T(n/2)=(n/2)^2\) dando um total de \(\frac{5}{16}n^2\).

Segunda geração: \(T(n/16)=(n/16)^2\), \(T(n/8)=(n/8)^2\), \(T(n/8)=(n/8)^2\), \(T(n/4)=(n/4)^2\) dando um total de \(\frac{25}{256}n^2\).

Logo, o custo total é

\((1+ 5/16 + 25/256 + \cdots)n^2 =\frac{n^2}{1-5/16}\in O(n^2)\)

...