Questão 67452

Um professor de Algoritmos e Estruturas de Dados está explicando sobre a complexidade de algoritmos e a notação Big-O. Ele quer que seus alunos compreendam que, para grandes volumes de dados, a ordem de crescimento da função de complexidade é muito mais importante do que as constantes ou os termos de ordem inferior. Para isso, ele apresenta a definição formal de Big-O e um exemplo prático. Ele explica: "Dizemos que $f(n)$ é $O(g(n))$ se existem constantes positivas $c$ e $n_0$ tais que $0 \le f(n) \le c \cdot g(n)$ para todo $n \ge n_0$. Em termos simples, isso significa que, para um $n$ suficientemente grande, $f(n)$ é limitada superiormente por um múltiplo de $g(n)$. Ao analisar a complexidade, focamos no termo de maior crescimento e ignoramos as constantes. Por exemplo, se o número de operações de um algoritmo for $T(n) = 3n^2 + 100n + 50$, sua complexidade em Big-O é $O(n^2)$." Ele então pede aos alunos para compararem dois algoritmos:

Algoritmo A: Tempo de execução de $T_A(n) = 500n + 1000$. Algoritmo B: Tempo de execução de $T_B(n) = 2n^2 + 10$.

Ele pergunta: "Qual algoritmo é mais rápido?"

Avaliando a complexidade assintótica dos dois algoritmos, analise as seguintes afirmações.

I. A complexidade do Algoritmo A é $O(n)$ (linear). A complexidade do Algoritmo B é $O(n^2)$ (quadrática).

II. Para valores pequenos de $n$ (ex: $n=10$), o Algoritmo B pode ser mais rápido que o A, pois suas constantes são menores ($T_A(10)=6000$, $T_B(10)=210$).

III. Para valores grandes de $n$, o Algoritmo A será sempre muito mais rápido que o Algoritmo B. A análise assintótica nos diz que, independentemente das constantes, uma função quadrática sempre crescerá muito mais rápido que uma função linear. Portanto, para problemas de grande escala, o Algoritmo A é assintoticamente mais eficiente.

É correto o que se afirma em: