Qual a ordem de complexidade no pior caso de:
n+raizn

Passo 1

O enunciado pede para determinar a ordem de complexidade no pior caso da expressão n + raizn. 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 f(n) está em O(g(n)) se há constantes c>0 e n0 tais que f(n) <= c,g(n) para todo n >= n0. 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 n cresce mais rápido que raizn à medida que ntoinfty. Em particular:
limntoinftyraiznn = limntoinfty n^-1/2 = 0

Passo 4

Isso mostra que raizn é assintoticamente negligenciável em comparação com n. Assim, na soma n + raizn, o termo dominante é n.

Resposta

O(n)

Exercícios relacionados