2a QUESTÃO Valor: 1,00 Supor que um algoritmo resolve o problema P e sua complexidade do pior caso f(n), sendo n o tamanho da entrada, verifica f =...

Para a primeira condição, temos que provar que f = O(n). Sabemos que f = O(n^4), o que significa que existe uma constante positiva c e um valor de n0 tal que f(n) <= c * n^4 para todo n >= n0. Podemos escolher c = 1 e n0 = 1. Assim, temos que f(n) <= n^4 para todo n >= 1. Como n^4 <= n^4 para todo n >= 1, podemos concluir que f = O(n). Para a segunda condição, temos que provar que f = Ω(n^5). Sabemos que f = Ω(n^2), o que significa que existe uma constante positiva c e um valor de n0 tal que f(n) >= c * n^2 para todo n >= n0. Podemos escolher c = 1 e n0 = 1. Assim, temos que f(n) >= n^2 para todo n >= 1. Como n^2 <= n^5 para todo n >= 1, podemos concluir que f = Ω(n^5). Para a terceira condição, temos que provar que f = Ω(n^3). Sabemos que f = Ω(n^2), o que significa que existe uma constante positiva c e um valor de n0 tal que f(n) >= c * n^2 para todo n >= n0. Podemos escolher c = 1 e n0 = 1. Assim, temos que f(n) >= n^2 para todo n >= 1. Como n^2 <= n^3 para todo n >= 1, podemos concluir que f = Ω(n^3).