Qual a ordem de complexidade no pior caso de:
Passo 1
O enunciado pede para determinar a ordem de complexidade no pior caso da expressão
. O conteúdo envolvido é notação assintótica (Big-O) e vamos precisar usar a regra que compara funções para identificar o termo dominante.
Passo 2
Em notação Big-O, dizemos que uma função
está em
se há constantes
e
tais que
para todo
. Além disso, para somas de termos, o crescimento é determinado pelo termo que cresce mais rápido.
Passo 3
Vamos comparar os dois termos da expressão. Sabemos que
cresce mais rápido que
à medida que
. Em particular:
Passo 4
Isso mostra que
é assintoticamente negligenciável em comparação com
. Assim, na soma
, o termo dominante é
.