MO640 - Questão para a prova oral

Número: 010

Enunciado: Dados dois algoritmos A e B para resolver um problema, sendo que o algoritmo A leva tempo f(N)=N² em qualquer entrada de tamanho N, e o algoritmo B leva g(N)=aN, onde a é uma constante, em qualquer entrada de tamanho N. Pode-se concluir que:

1. O algoritmo A sempre será mais rápido que B em virtude de ser quadrático, independendo do tamanho N do problema.
2. O algoritmo B sempre será mais rápido que A em virtude ser linear, independendo do tamanho N do problema.
3. Quando o tamanho N for menor que a, o algoritmo quadrático será mais rápido.
4. Quando o tamanho N for maior que a, o algoritmo quadrático será mais rápido.
5. NDA

Autor: Rodrigo Ritter.