Considere o pseudocódigo abaixo, que define uma função que recebe dois arrays, A1, A2, cada um com N elementos indexados a partir de 1, e retorna o número de elementos do array A1 que não aparecem em A2. function xpto(A1, A2, N) contagem=0 for i=1 to N flag=0 for j=1 to N if A1[i] == A2[j] then flag=1 if flag == 0 then contagem=contagem + 1 return contagem Exatamente como foi codificado, o algoritmo da função xpto tem complexidade
- A)O(1)
Errada, porque o algoritmo não faz um número fixo de operações; ele percorre os arrays proporcionalmente ao tamanho N.
- B)O(n)
Errada, porque há um laço dentro do outro, então o crescimento não é linear.
- C)O(2.n)
Errada, porque 2.n ainda é linear e ignora o efeito do laço interno multiplicando o trabalho.
- D)O(n²)
Certa, porque dois laços aninhados de tamanho N geram complexidade quadrática.
- E)O(2.n²)
Errada, porque o fator 2 é constante e não muda a ordem assintótica, ficando apenas O(n^2).
Gabarito: D
A ideia da função é simples: para cada elemento de A1, ela percorre todo o array A2 procurando se existe algum igual. Se encontrar, marca uma flag; se não encontrar, soma 1 na contagem. Isso já entrega a cara do algoritmo: um laço dentro do outro, ambos indo de 1 até N. Quando você tem dois loops aninhados, cada um com N execuções, o número de comparações cresce na ordem de N vezes N. Em análise assintótica, a parte dominante é N^2, então a complexidade é quadrática. Os comandos de atribuição e teste de flag são constantes e não mudam essa ordem. Por isso, a resposta certa é a alternativa D. Mesmo que existam detalhes como a posição do return no enunciado, a intenção da questão é avaliar a complexidade do código exatamente como está estruturado com dois for. E dois for completos, cada um dependente de N, significam O(n^2). Em prova, a FGV costuma cobrar justamente isso: não basta olhar para uma linha isolada, você precisa enxergar o efeito da repetição. Se o algoritmo compara cada elemento de um vetor com todos os elementos do outro, a conta quase sempre sobe para quadrática.