Qual a ordem de complexidade no pior caso de:
Passo 1
O enunciado pede para determinar a ordem de complexidade no pior caso da função
. O assunto aqui é análise de algoritmos usando notação Big-O.
Passo 2
A notação Big-O caracteriza o comportamento assintótico superior de uma função quando
cresce muito. Formalmente, dizemos que
é
se existem constantes positivas
e
tais que, para todo
, temos
.
Passo 3
Para aplicar ao nosso caso, note que
para
, isto é,
. Logo, basta escolher
e
para garantir
sempre que
. Portanto,
é
.