Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo a(n)=n^2-n+549 e b(n)=49 n+49, respectivamente. Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do que B.

Passo 1

O enunciado dá duas funções de tempo a(n)=n^2 - n + 549 e b(n)=49n + 49 e pede os naturais n tais que a(n). Vamos usar teoria de inequações quadráticas para resolver isso.

Passo 2

Primeiro montamos a inequação comparando as duas funções:
n^2 - n + 549 < 49n + 49
e então trazemos tudo para o lado esquerdo.

Passo 3

Ao reorganizar, temos:
n^2 - n - 49n + 549 - 49 < 0
ou seja
n^2 - 50n + 500 < 0.

Passo 4

Para resolver n^2 - 50n + 500 = 0, usamos a fórmula de Bhaskara. O discriminante é
De
As raízes são
n = 50 pm raiz5002 = 50 pm 10raiz52

Passo 5

Essas raízes valem aproximadamente
n1 approx 13,82 e n2 approx 36,18
Como o coeficiente de n^2 é positivo, a parábola fica abaixo de zero justamente no intervalo entre as raízes.

Passo 6

Portanto, para naturais n a condição n^2 - 50n + 500 < 0 vale quando
13,82 < n < 36,18
Logo, os valores de n naturais que satisfazem são n=14,15,dots,36.

Resposta

Os naturais n tais que o algoritmo A é mais rápido que B são 14,15,dots,36.

Exercícios relacionados