Camila Duarte
31/12/1969 • 21:00
Gabarito: e)
Vamos analisar cada alternativa para entender por que a letra e é a correta.
a) O limite inferior de um algoritmo é representado pela notação ômega (Ω), e não pela notação O. A notação O é usada para o limite superior, ou seja, para analisar o pior caso. Portanto, a afirmativa está incorreta.
b) A definição correta para uma função f(n) dominar assintoticamente g(n) é que existem constantes positivas c e n0 tais que para todo n >= n0, |g(n)| <= c|f(n)|. A alternativa fala em igualdade para n = n0, o que não corresponde à definição correta. Logo, está errada.
c) A função f(5log2 N) é uma função logarítmica multiplicada por uma constante, o que é O(log N), e não O^2(N) (que não é uma notação padrão). Portanto, essa alternativa está incorreta.
d) A função f(5N^3 + 2N^2) tem como termo dominante N^3, logo é O(N^3), não O(N). Portanto, essa alternativa está errada.
e) Se duas funções f e g têm limite superior justo, isso significa que f é O(g) e g é O(f), ou seja, elas são assintoticamente equivalentes. Essa afirmativa está correta e é a resposta correta da questão.
Checagem dupla confirma que a letra e é a única alternativa correta segundo a definição formal de notação assintótica e análise de algoritmos.
Vamos analisar cada alternativa para entender por que a letra e é a correta.
a) O limite inferior de um algoritmo é representado pela notação ômega (Ω), e não pela notação O. A notação O é usada para o limite superior, ou seja, para analisar o pior caso. Portanto, a afirmativa está incorreta.
b) A definição correta para uma função f(n) dominar assintoticamente g(n) é que existem constantes positivas c e n0 tais que para todo n >= n0, |g(n)| <= c|f(n)|. A alternativa fala em igualdade para n = n0, o que não corresponde à definição correta. Logo, está errada.
c) A função f(5log2 N) é uma função logarítmica multiplicada por uma constante, o que é O(log N), e não O^2(N) (que não é uma notação padrão). Portanto, essa alternativa está incorreta.
d) A função f(5N^3 + 2N^2) tem como termo dominante N^3, logo é O(N^3), não O(N). Portanto, essa alternativa está errada.
e) Se duas funções f e g têm limite superior justo, isso significa que f é O(g) e g é O(f), ou seja, elas são assintoticamente equivalentes. Essa afirmativa está correta e é a resposta correta da questão.
Checagem dupla confirma que a letra e é a única alternativa correta segundo a definição formal de notação assintótica e análise de algoritmos.