MO417 - Questão para a prova oral

Número: 2003-032

Enunciado: A solução da recorrência T(n) = 2T(n/2) + n é:

A) O(n)
B) O(lg n)
C) Ω(n^2)
D) Θ(lg n)
E) NDA

Ideia original de: Alexandro Baldassin