MO417 - Questão para a prova oral

Número: 2003-024

Enunciado: Considere uma função f(n) que satisfaz:
    f(n) = O(n^2)
    f(n) = ω(lg(n))
Qual alternativa contém duas funções que poderiam ser f(n)?

A) n! e n^2
B) (lg(n))! e n^n
C) n^(lg(lg(sqrt(64)))) e lg(n) * lg(n)
D) não existe nenhuma função conhecida que possa ser f(n)
E) n.d.a.

Obs.: sqrt(x) é a raiz quadrada de x


Ideia original de: Ricardo Luís Lachi