GabaritoD — 9
Gabarito: letra D. O menor valor de c que satisfaz (f(n) \leq c \cdot n^3) para todo (n \geq 1) é 9, pois o pior caso ocorre em (n=1), onde (f(1)=9), e a constante deve ser ao menos esse valor para que a desigualdade se mantenha em todo o domínio.
A questão trata do conceito de notação Big-O e dominação assintótica. Dada (f(n) = 3n^3 + 4n^2 + 2n), queremos encontrar a menor constante c tal que (c \cdot n^3) seja um limitante superior de (f(n)) para todos os valores de (n) a partir de 1 (pois o enunciado fixa (n \geq 1)).
A condição é:
[3n^3 + 4n^2 + 2n \leq c \cdot n^3]
Dividindo ambos os lados por (n^3) (válido para (n>0)):
[3 + \frac{4}{n} + \frac{2}{n^2} \leq c]
Como a expressão da esquerda é decrescente em (n) (os termos (\frac{4}{n}) e (\frac{2}{n^2}) diminuem quando (n) aumenta), o maior valor ocorre no menor (n) do intervalo, ou seja, (n=1):
Para (n=1): (3 + 4 + 2 = 9)
Portanto, (c) deve ser pelo menos 9. Com (c=9), verifica-se que a desigualdade vale para todos (n \geq 1):
(n=1): (9 \leq 9) ✓
(n=2): (3\cdot8 + 4\cdot4 + 2\cdot2 = 24+16+4=44 \leq 9\cdot8=72) ✓
Para (n) grande, o termo dominante (3n^3) é menor que (9n^3) ✓
Nenhum valor menor que 9 funciona (por exemplo, (c=8) falha em (n=1): (9 > 8)). Assim, 9 é o menor inteiro positivo que satisfaz a condição.
Em problemas de dominação assintótica com polinômios, o pior caso (maior razão (f(n)/g(n))) geralmente ocorre no menor (n) do intervalo, pois os termos de menor ordem (como (n^2) e (n)) têm peso relativo maior quando (n) é pequeno. Teste sempre o menor (n) do domínio (aqui (n=1)) para encontrar a constante mínima.
Gabarito: letra D.
Link permanente: /questoes/qq283602