A respeito de funções e algoritmos, assinale a afirmativa correta.

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.