Coloque F (falso) ou V (verdadeiro) nas funções abaixo, con...

A alternativa correta é: B - (V) (V) (F) (V).

Para resolver essa questão, precisamos entender a notação de complexidade Big O, que é usada para classificar algoritmos de acordo com o seu comportamento de crescimento, especialmente em termos de tempo ou espaço, à medida que o tamanho da entrada aumenta.

Vamos analisar cada uma das funções fornecidas:

(1) f - 9 + log(n) = O(n)

Esta afirmação é falsa. A função log(n) cresce muito mais lentamente do que n. Portanto, a complexidade não pode ser O(n).

(2) f = 255 = O(1)

Esta afirmação é verdadeira. O valor constante (255) tem complexidade O(1), pois não depende de n. Independente do tamanho da entrada, a operação é constante.

(3) f = 37 + 2¹⁵ⁿ = O(2ⁿ)

Esta afirmação é falsa. A função 2¹⁵ⁿ cresce exponencialmente mais rápido que 2ⁿ devido à presença do multiplicador 15. Portanto, não podemos dizer que é O(2ⁿ).

(4) f = 25 + 2¹⁸⁺ⁿ = O(2ⁿ)

Esta afirmação é verdadeira. Aqui, a função é equivalente a 2ⁿ multiplicada por uma constante (2¹⁸), o que não altera a classe de complexidade, mantendo-se O(2ⁿ).

Ao analisar cada função, verificamos que as afirmações corretas são as correspondentes à alternativa B.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

Quando se fala de complexidade utilizando o BIG O, pode-se desprezar constantes aditivos e multiplicativas.

Nesse caso a questão está querendo saber qual é a complexidade de pior caso. Para saber isso é necessário saber quais são as possíveis complexidades e sua ordem.

O(1) = Constante

O(log n) = logarítmica

O(log^2 n) = log quadrática

O(n log n) = n log n

O(n) = linear

O(n^2) = quadrática

O(n^3) = cubica

O(2^n) = exponencial

================================

f - 9 + log n = 0(n) => CERTO

f= 255 = 0(1) => CERTO

f = 37 + 215n = 0(2n) => ERRADO - O(2^15N) possui a maior complexidade que a O(2^n)

f=25 + 218+n = 0(2n) => CERTO

Alternativa: B