MO417 - Questão para a prova oral

Número:

Enunciado: Sobre a notação O, Ω e algoritmos, assinale V para verdadeiro e F para falso:

(  ) O (lê-se o maiúsculo) fornece um limite assintótico superior e é formalmente definido como O(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ f(n) ≤ cg(n) para todo n>n₀}
(  ) Ao contrário de O (lê-se o maiúsculo), Ω fornece um limite assintótico inferior e é formalmente definido como Ω(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ cg(n) < f(n) para todo n>n₀}
(  ) Um limite inferior para um problema P é uma função h(n). Todo algoritmo que resolve P efetua pelo menos Ω(h(n)) operações.
(  ) Dado um problema P, se P é Ω(h(n)) e encontramos um algoritmo A com complexidade O(h(n)) entao A é um algoritmo ótimo para P.
(  ) O tempo de execução do algoritmo selection_sort para o pior caso é O(n²) e para o melhor caso O(n)


a. V - V - V F - V
b. F - F - F - V - F
c. V - F - F - F - V
d. V - F - V - V - F
e. NDA

Ideia original de: Lucas Oliveira Batista