Com base no código, a complexidade de tempo do algoritmo em notação O-Grande (Big-O) é:GabaritoD — O(n²)
Gabarito: letra D. A complexidade de tempo do algoritmo é O(n²), pois o trecho de código apresenta dois laços aninhados que iteram sobre a mesma entrada de tamanho n, resultando em aproximadamente n × n = n² operações. Essa é a análise clássica de complexidade para laços aninhados independentes, conforme o conceito de notação Big-O.
A notação Big-O descreve o comportamento assintótico de um algoritmo, ou seja, como o tempo de execução (ou uso de memória) cresce à medida que o tamanho da entrada aumenta. Ela ignora constantes multiplicativas e termos de ordem inferior, focando no termo dominante. Para analisar a complexidade, contamos o número de operações básicas (como comparações e atribuições) em função do tamanho da entrada n.
No caso de laços aninhados, a complexidade é o produto do número de iterações de cada laço. Se um laço externo executa n vezes e, para cada iteração, um laço interno também executa n vezes, o total de iterações é n × n = n². Isso resulta em complexidade quadrática, O(n²).
Um exemplo concreto: se n = 100, o laço interno executa 100 vezes para cada uma das 100 iterações do externo, totalizando 10.000 iterações. Se n = 1000, são 1.000.000 de iterações. O crescimento é proporcional ao quadrado do tamanho da entrada, o que torna o algoritmo inviável para entradas muito grandes.
A pegadinha comum nesta questão é confundir a complexidade de laços aninhados com a de algoritmos de ordenação eficientes (como Merge Sort, O(n log n)) ou com a de um único laço (O(n)). A presença de dois laços aninhados, ambos percorrendo a entrada de tamanho n, é o indicador direto de O(n²).
Guarde o critério decisivo: conte quantos laços aninhados percorrem a entrada de tamanho n. Um laço → O(n); dois laços aninhados → O(n²); três → O(n³). É exatamente essa contagem que separa as alternativas desta questão.
O(1) indica complexidade constante, ou seja, o tempo de execução não depende do tamanho da entrada. Isso ocorreria se o algoritmo executasse um número fixo de operações, independentemente de n. No código apresentado, há laços que iteram sobre a entrada, então o tempo cresce com n. A alternativa confunde operações de tempo constante (como acessar um elemento de array por índice) com a execução de laços.
O(n) indica complexidade linear, típica de um único laço que percorre a entrada uma vez. No código, há dois laços aninhados, o que multiplica o número de iterações. Se houvesse apenas um laço, a complexidade seria O(n), mas a presença do segundo laço interno eleva para O(n²). A alternativa ignora o aninhamento.
O(n log n) é a complexidade de algoritmos de ordenação eficientes, como Merge Sort e Heap Sort. Essa complexidade surge em algoritmos que dividem o problema em partes menores (log n) e processam cada parte linearmente (n). No código, não há divisão da entrada; apenas iterações completas sobre ela em dois níveis, o que não gera o fator logarítmico. A alternativa confunde a complexidade de ordenação com a de laços aninhados.
O(n²) é a complexidade quadrática, resultante de dois laços aninhados que percorrem a entrada de tamanho n. Para cada iteração do laço externo, o laço interno executa n vezes, totalizando n × n = n² operações. Essa é a análise correta para o código apresentado, que contém exatamente dois laços aninhados.
O(n!) indica complexidade fatorial, que cresce extremamente rápido e é típica de algoritmos que geram todas as permutações de um conjunto, como o problema do caixeiro viajante por força bruta. No código, não há geração de permutações nem recursão; apenas laços aninhados. A alternativa confunde a complexidade de algoritmos combinatórios com a de iterações simples.
Gabarito: letra D
Link permanente: /questoes/fg078366