Questão de Análise de Sistemas · CESGRANRIO BNDES 01/2024 (nº 55)

Conceito-chave: Complexidade assintótica $O(n)$ descreve como o tempo cresce com o tamanho da entrada, mas ignora constantes multiplicativas e custos fixos por operação. Dois algoritmos $O(n)$ podem ter tempos reais muito diferentes: um com operação interna cara ($k \cdot t_D$) demora mais que um com operação barata ($t_C$), mesmo ambos sendo lineares.

• (A) Incorreta: Algoritmo 1 é o mais simples possível: uma única operação $O(1)$ por elemento, sendo o menos custoso entre os listados.
• (B) Incorreta: Algoritmo 2 faz duas iterações separadas, mas cada uma com operação $O(1)$; o tempo total é $2 \cdot n \cdot c$, ainda pequeno comparado aos que têm operações internas caras.
• (C) Incorreta: Algoritmo 3 tem operação interna de custo fixo $t_C$; como $t_C$ é menor que $k \cdot t_D$, ele é mais rápido que o Algoritmo 4.
• (D) Correta: Algoritmo 4 tem operação interna com custo $k \cdot t_D$, onde $k \cdot t_D > t_C$. Como esse custo se repete $n$ vezes, o tempo real é $n \cdot k \cdot t_D$, que é maior que $n \cdot t_C$ (Algoritmo 3) e que $2n \cdot c$ (Algoritmo 2). A pegadinha: a banca quer que você perceba que $O(n)$ não significa "mesmo tempo" — apenas "mesma taxa de crescimento". O Algoritmo 4 tem a mesma classe assintótica, mas a maior constante, tornando-o o menos eficiente na prática.
• (E) Incorreta: Algoritmo 5 é idêntico ao Algoritmo 1 em essência: operação $O(1)$ por elemento, sem custo extra relevante.