Questão 66160

Uma professora de Algoritmos e Estruturas de Dados em um curso de graduação em Computação está frustrada com a forma como seus alunos abordam a análise de complexidade de algoritmos. Eles conseguem aplicar as 'regras de bolso' para calcular a notação Big-O em laços simples e aninhados, mas falham em desenvolver uma intuição sobre o que a complexidade assintótica realmente significa em termos práticos. Eles frequentemente assumem, por exemplo, que um algoritmo $O(n \log n)$ é *sempre* mais rápido que um algoritmo $O(n^2)$, independentemente do tamanho da entrada ou das constantes envolvidas. Para combater essa concepção equivocada, ela desenha um experimento. Ela apresenta aos alunos um trecho de um artigo clássico de Jon Bentley, "Programming Pearls": "A análise de complexidade nos diz como o tempo de execução escala com o tamanho da entrada, o que é crucial para entradas grandes. No entanto, para entradas pequenas, a simplicidade e as constantes ocultas na notação Big-O podem dominar. Um algoritmo de ordenação por inserção, com complexidade $O(n^2)$, pode superar um Quicksort, $O(n \log n)$, para $n < 20$ em certas implementações, devido à sua baixa sobrecarga (overhead). Compreender esse 'ponto de virada' é uma marca da maturidade de um engenheiro de software, que sabe que a melhor solução teórica nem sempre é a melhor solução prática." A professora, então, pede que os alunos implementem dois algoritmos: Insertion Sort ($O(n^2)$) e Merge Sort ($O(n \log n)$). A tarefa é escrever um programa que meça o tempo de execução de ambos para diferentes tamanhos de entrada (n=10, 50, 100, 1.000, 10.000, 100.000) e plotar os resultados em um gráfico, identificando o ponto aproximado onde o Merge Sort se torna consistentemente mais rápido.

Com base na situação-problema e no referencial teórico de Bentley, qual é a principal competência que a professora pretende desenvolver em seus alunos com esta atividade?