Algoritmos e Estrutura de Dados · FGV · 2021 | Questão sqc-fg039322

Complexidade do algoritmo: laços aninhados

Gabarito: letra D. O algoritmo possui dois laços for aninhados, cada um iterando N vezes, resultando em $N \times N = N^2$ operações elementares no pior caso. Portanto, a complexidade assintótica é $O(N^2)$ , independentemente de constantes multiplicativas.

A função xpto percorre cada elemento de A1 (laço externo) e, para cada um, percorre todo o array A2 (laço interno) para verificar se o elemento aparece. Isso gera exatamente $N \times N = N^2$ comparações entre elementos. As operações de atribuição e incremento são desprezíveis na análise assintótica. Assim, a complexidade é quadrática.

1Laço externo: N iterações
2Laço interno: N iterações
3Total: N × N = N²
4Big-O: O(N²)

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

$O(1)$ seria constante, o que não ocorre porque o tempo de execução cresce com o tamanho da entrada.

Alternativa B — ❌ Incorreta

$O(n)$ seria linear, mas o algoritmo tem dois laços aninhados, não um único laço.

Alternativa C — ❌ Incorreta

$O(2n)$ ainda é linear (constante ignorada). O algoritmo é quadrático, não linear.

Alternativa D — ✅ Correta ⟵ GABARITO

$O(n^2)$ representa exatamente a complexidade dos dois laços aninhados, cada um iterando $N$ vezes.

Alternativa E — ❌ Incorreta

$O(2n^2)$ é equivalente a $O(n^2)$ , mas a notação Big-O desconsidera constantes multiplicativas. Embora tecnicamente correto como limite superior, a forma padrão e mais simples é $O(n^2)$ . A banca considerou a notação simplificada; $O(n^2)$ é a resposta esperada.

PEGA ESSA DICA!

Em análise de complexidade, foque no termo dominante e ignore constantes. Laços aninhados sem interrupções indicam complexidade multiplicativa: externo $N$ , interno $N$ , total $N^2$ .

Gabarito: letra D – $O(n^2)$ .