Questão 765654

A notação “O” que determina ordem de complexidade e eficiência de um algoritmo pode ser formalizada como se segue:

\(T(n)=0(f(n))\)

Se existirem m inteiro e c constante tais que

\(T(n)\le cf\ (n)\ para\ n>m.\)

Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes algoritmos. Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém utilizando algoritmos diferentes.

Considere as seguintes ordens de complexidade no tempo:

T1(n) = n, T2(n) = nlogn, T3(n) = n² , T4(n) = 2ⁿ