Questão 20 — Complexidade de Algoritmos — Notação O (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2025

Algoritmos e Estruturas de Dados Complexidade de Algoritmos — Notação O

Serviço de Seleção do Pessoal da Marinha (SSPM) 2025

Marinha do Brasil · Quadro Técnico do Corpo Auxiliar da Marinha (CP-T) — Informática · Caderno Amarela

Gabarito disponível

Reescreva as funções de tempo apresentadas abaixo em Notação O e assinale a opção correta.

2ⁿ + n³ ; 305 ; (n − 1)ⁿ + nⁿ⁻¹; log(n!) ; 5n + 10; 2ⁿ + n² + 100n + 50

Selecione uma alternativa A) O(2ⁿ) ; O(1) ; O(nⁿ) ; O(nlog(n)) ; O(n) ; O(2ⁿ). B) O(2ⁿ) ; O(n) ; O(nⁿ⁻¹) ; O(nⁿ) ; O(n) ; O(n²). C) O(n³) ; O(1) ; O(nⁿ) ; O(nⁿ); O(n) ; O(2ⁿ). D) O(n³) ; O(n) ; O(nⁿ) ; O(nlog(n)); O(n) ; O(n²). E) O(n³) ; O(1) ; O(nⁿ⁻¹) ; O(nⁿ); O(n) ; O(2ⁿ).

Resolução comentada

Mantém-se o termo dominante: O(2ⁿ), O(1), O(nⁿ), O(n log n), O(n), O(2ⁿ).

Em 2ⁿ + n³ domina 2ⁿ; 305 é constante, O(1). Em (n−1)ⁿ + nⁿ⁻¹ domina nⁿ. Como log(n!) ≈ n·log n, é O(n log n). 5n + 10 é O(n), e em 2ⁿ + n² + 100n + 50 domina 2ⁿ.

Análise das alternativas

B, C, D e E) Erradas: trocam o termo dominante (por exemplo, n³ no lugar de 2ⁿ), classificam a constante como O(n), ou dão O(nⁿ⁻¹) ou O(n²) onde o termo dominante é outro.

Referência: Análise de algoritmos: notação O e termos dominantes.

Resolução comentada do VaiConcursos.