Questão FC514956
Em relação à complexidade de algoritmos (notação Big-O) e à programação em Python para processamento de sinais, julgue o item que se segue. O tempo de execução de um algoritmo com
Algoritmos e Lógica de Programação
CEBRASPE (CESPE) · 2025
Em relação à complexidade de algoritmos (notação Big-O) e à programação em Python para processamento de sinais, julgue o item que se segue.
O tempo de execução de um algoritmo com complexidade O(n²) cresce linearmente com a entrada n.
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
A afirmação foi julgada ERRADO porque confunde crescimento linear com crescimento quadrático. Em notação Big‑O estamos tratando de complexidade de tempo, ou seja, como o tempo de execução escala com o tamanho da entrada n.
Um algoritmo com O(n) cresce de forma linear: dobrar n tende a dobrar o tempo. Já um algoritmo com O(n^2) tem crescimento quadrático. Matematicamente, se \(T(n)=c\,n^2\), então \(T(2n)=c(2n)^2=4c\,n^2\): dobrar a entrada aumenta o tempo por um fator quatro, não dois.
Um caso prático típico é um laço aninhado (for i in range(n): for j in range(n): ...), que realiza ~\(n^2\) operações. Portanto afirmar que O(n^2) cresce linearmente é incorreto; o crescimento é quadrático.
Conteúdo do catálogo FC Concursos · Atualizado em