Análise de Complexidade Assintótica (Notação Big-O)
Gabarito: letra C – estão corretas as afirmativas II, III, IV e V. A afirmativa I é falsa porque inverte a relação: se g(n) = O(f(n)), então f(n) é um limite superior para g(n), mas não se pode afirmar que um algoritmo com complexidade f(n) tenha ordem g(n); a ordem deve ser no máximo f(n), e não g(n) (que é menor ou igual).
Vamos analisar cada afirmativa:
Afirmativa I — ❌ Incorreta
Interpretação: "Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de complexidade g(n)". Isso está errado. A definição de O-grande diz que g(n) ≤ c·f(n) para n grande, ou seja, f(n) é um limite superior para g(n). Um algoritmo com complexidade f(n) pode ter ordem O(f(n)), não necessariamente O(g(n)) – na verdade, se g(n) cresce mais lentamente, o algoritmo pode ser até Ω(g(n)), mas não O(g(n)) a menos que sejam assintoticamente iguais. Exemplo: f(n)=n², g(n)=n: g=O(f) é verdade, mas um algoritmo O(n²) não é O(n). Portanto, a afirmativa é falsa.
Afirmativa II — ✅ Correta
Se g(n) = O(f(n)), então existem constantes c e n₀ tais que g(n) ≤ c·f(n) para todo n ≥ n₀. Isso significa que f(n) é um limite superior (a menos de constante) para g(n). A afirmativa está correta.
Afirmativa III — ✅ Correta
g(n) = 7 log n + 6. Para n grande, 7 log n + 6 ≤ 8 log n (para log n ≥ 6), logo g(n) = O(log n). De fato, termos constantes e aditivos não afetam a ordem assintótica. Portanto, correta.
Afirmativa IV — ✅ Correta
g(n)=n² e f(n)=(n+1)² = n²+2n+1. Temos que g(n) ≤ f(n) para todo n, então g=O(f). Por outro lado, f(n) ≤ 2n² para n ≥ 3 (pois n²+2n+1 ≤ 2n² quando n² ≥ 2n+1, vale para n≥3), logo f=O(g). Assim, ambas são O uma da outra, o que significa que estão na mesma classe de complexidade (Θ(n²)). Afirmativa correta.
Afirmativa V — ✅ Correta
g(n)=2^{n+1} = 2·2^n, e f(n)=2^n. Como g(n) = 2·f(n), temos g(n) ≤ 3·f(n) para n ≥ 0, portanto g=O(f). A afirmativa está correta.
Conclusão: Estão corretas II, III, IV e V. A alternativa que contém exatamente essas é a C (II, III, IV, V).