Alternativa D
A questão aborda a análise de complexidade algorítmica, especificamente do algoritmo Bubble Sort.
Entendendo a Complexidade Quadrática
O enunciado fornece uma pista fundamental: ele descreve o tempo computacional variando de forma quadrática com o tamanho da entrada.
- Entrada (n): Representa o número de elementos a serem ordenados.
- Tempo Quadrático: Significa que, se dobrarmos o tamanho da entrada, o tempo de processamento será multiplicado por quatro ($2^2 = 4$).
- Representação Matemática: No cálculo assintótico (Notação Big-O), o termo "quadrático" é representado pelo expoente 2.
Portanto, a expressão matemática para complexidade quadrática é:
O(n^2)
Por que o Bubble Sort tem essa complexidade?
O algoritmo Bubble Sort funciona comparando pares de elementos adjacentes e trocando-os se estiverem na ordem incorreta. Para garantir que todos os elementos estejam ordenados, ele precisa percorrer a lista repetidamente.
Isso ocorre porque:
- O algoritmo utiliza dois laços (loops) aninhados.
- O primeiro laço itera sobre cada elemento da lista.
- O segundo laço compara esse elemento com os restantes.
Se considerarmos n elementos:
- O número total de comparações no pior caso é aproximadamente n \times n.
- Isso resulta em n^2 operações básicas.
Resumo das Opções
| Letra | Notação | Tipo de Complexidade | Exemplo Comum |
|---|
| A | O(\log n) | Logarítmica | Busca Binária |
| B | O(n \log n) | Linear-Logarítmica | Merge Sort |
| C | O(n) | Linear | Busca Sequencial |
| D | $O(n^2)$ | Quadrática | Bubble Sort |
| E | O(n^3) | Cúbica | Multiplicação de Matrizes |
Como o enunciado pede explicitamente a representação da variação quadrática, a única opção correta é a que contém o expoente 2.
Alternativa D.