Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo
e
, respectivamente. Determine quais são os valores de
pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do que
.
Passo 1
O enunciado dá duas funções de tempo
e
e pede os naturais
tais que
. Vamos usar teoria de inequações quadráticas para resolver isso.
Passo 2
Primeiro montamos a inequação comparando as duas funções:
e então trazemos tudo para o lado esquerdo.
Passo 3
Ao reorganizar, temos:
ou seja
Passo 4
Para resolver
, usamos a fórmula de Bhaskara. O discriminante é
As raízes são
Passo 5
Essas raízes valem aproximadamente
Como o coeficiente de
Passo 6
Portanto, para naturais
a condição
vale quando
Logo, os valores de
Resposta
Os naturais
tais que o algoritmo A é mais rápido que B são
.