Questão 16 Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números reais positivos.
Com respeito às notações assintóticas de complexidade, avalie as afirmativas abaixo.

A análise permite concluir que
a) todas as afirmativas são falsas.
b) todas as afirmativas são verdadeiras.
c) apenas as afirmativas I e III são verdadeiras.
d) apenas as afirmativas II e IV são verdadeiras.
e) apenas a afirmativa V é falsa.
(para melhor visualização dos itens clique na imagem)
Gabarito: b (Selecione o texto a esquerda para ver a resposta ou consulte o fim do post).

Explicação: Esta questão mostra exatamente as definições dessas notações. A única coisa que posso salientar é a necessidade de saber uma das diferenças entre O e "ozinho" e Omega e "Omegazinho", na O e Omega precisamos apenas de uma constante real c>0 já para "Omegazinho e Ozinho" precisamos que funcione para toda constante real c>0, que é exatamente o que os itens dizem.

Logo, todas estão corretas, alternativa b.

Para mais detalhes sobre essa questão consultem "Algoritmos, Teoria e Prática" (O livrão da Capa Vermelha, todo estudante de computação já deve ter estudado por ele), Cormen et al., 2001, nas páginas 32-49 ele define todas essas notações.

Não concorda? Comente, opine e demonstre seu conhecimento!

Gabarito: b