Alternativa E - O(1)
Análise da Complexidade
Para determinar a complexidade de um algoritmo usando a notação Big-O, analisamos como o tempo de execução cresce à medida que o tamanho da entrada dos dados aumenta.
1. Comportamento do Código
O código apresenta um laço for definido da seguinte forma:
\text{for (int n = 0; n < 100; n++)}
- Número de Iterações Fixo: O laço executa exatamente 100 vezes.
- Sem Variável de Entrada: Não existe uma variável externa (como
tamanho ou N) controlando o limite do loop. O número 100 é uma constante.
2. Conceito de Complexidade Constante
Na teoria da complexidade algorítmica, quando o tempo de execução não depende do tamanho da entrada (pois não há entrada variável), dizemos que a complexidade é constante.
- Independentemente de quantas vezes você execute o programa, ele sempre fará aproximadamente as mesmas operações (100 verificações).
- Matematicamente, constantes são ignoradas no Big-O. Se o loop rodasse 1 milhão de vezes, ainda seria O(1), pois o crescimento é zero.
3. Por que as outras alternativas estão incorretas?
| Notação | Significado | Aplicabilidade neste caso |
|---|
| $O(n)$ | Linear | Só seria correta se o limite fosse uma variável de entrada (ex: i < N). |
| $O(\log n)$ | Logarítmica | Típico de buscas binárias ou divisão recursiva. |
| $O(1)$ | Constante | Correta. O tempo é fixo, independente de entradas externas. |
Nota Importante: O uso da variável n no código pode confundir. Na notação O(n), o símbolo n refere-se ao tamanho do input, não necessariamente ao nome da variável no código. Como não há input variável aqui, o n do código é apenas um contador local.
Portanto, a complexidade é $O(1)$.