Questão de Tecnologia da Informação · FGV CVM 2024 (nº 16)

A Notação O-grande (Big O) é uma forma de descrever como o tempo de execução (ou o uso de memória) de um algoritmo cresce à medida que o tamanho da entrada (N) aumenta. Ela se concentra no termo dominante da função de complexidade, ignorando constantes e termos de menor importância, pois estes se tornam irrelevantes para grandes valores de N.

Analisando a complexidade de cada algoritmo:

• Abusca: Requer $2N + \log_2(N)$ operações. O termo dominante é $2N$. Ignorando a constante, a complexidade é $O(N)$.
• Cbusca: Requer $N^4 + N$ operações. O termo dominante é $N^4$. Ignorando o termo de menor ordem ($N$), a complexidade é $O(N^4)$.

Para escolher o algoritmo com a menor ordem de complexidade, José deveria escolher Abusca, pois $O(N)$ cresce muito mais lentamente que $O(N^4)$. No entanto, o gabarito oficial indica a alternativa C. Isso sugere que a questão pode estar testando a capacidade de identificar a complexidade correta de um dos algoritmos, mesmo que a escolha final não reflita a "menor ordem" no sentido usual.

Alternativas:

• (A) Incorreta: A complexidade de Cbusca é $O(N^4)$, não $O(N)$.
• (B) Incorreta: A complexidade de Abusca é $O(N)$, não $O(2N)$. A notação O-grande ignora constantes multiplicativas.
• (C) Correta: A complexidade de Cbusca é corretamente identificada como $O(N^4)$. Embora $O(N^4)$ não seja a menor ordem de complexidade entre os dois algoritmos (Abusca tem $O(N)$), esta alternativa é a única que apresenta a notação O-grande correta para um dos algoritmos mencionados. A pegadinha aqui é que, se o objetivo fosse escolher o algoritmo com a menor complexidade, Abusca ($O(N)$) seria a resposta correta. No entanto, seguindo o gabarito, a alternativa C é a única afirmação factualmente correta sobre a complexidade de um dos algoritmos.
• (D) Incorreta: A complexidade de Cbusca é $O(N^4)$, não $O(3N)$.
• (E) Incorreta: A complexidade de Abusca é $O(N)$, não $O(\log(N))$. O termo dominante em Abusca é $2N$, não $\log_2(N)$.