MO417 - Questão para a prova oral

Número: 2009-005

Enunciado: Considere a relação de recorrência:

T(n) = {	c,	se n = 1
	T(n/2) + c,	se n > 1,

onde c é uma constante positiva. A solução para esta relação pertence a qual ordem de crescimento?

1. Θ(log n)
2. Θ(n)
3. Θ(n log n)
4. Θ(n²)
5. NDA

Ideia original de: Ana Carolina Correia Rézio