MO417 - Questão para a prova oral

Número: 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 numérica. Esta relação pertence a qual ordem crescimento?

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

Autor(a): Ana Carolina Correia Rézio