Semana: 03/03/2003 a 07/03/2003
Assunto: Recorrências
Considere a seguinte função de recorrência:
/ 1, se n = 1;
T(n) = | ____________________
| | (n + 1)(n - 1) + 1
\ 2 * T( | ------------------ ), para n > 1.
\| 4
_
Obs: ( \| ) foi utilizado para indicar a Raíz Quadrada.
A solução para esta recorrência é:
A) O( lg n )
B) Teta( n )
C) O( 2^(n/2) )
D) Teta( n lg n )
E) n.d.a.
Autor: Nielsen Cassiano Simões
RA: 941614