Questão 708919: A notação “O” que determ...

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

T(n) = O (ƒ(n))

Se existirem inteiro m e constante c tais que

T(n) ? cƒ(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 n