Question

Você analisou o tempo de execução de dois algoritmos e chegou à seguinte conclusão: o algoritmo A apresenta um tempo de execução na ordem de f(n) = 10n em relação ao tamanho da entrada n, enquanto o algoritmo B apresenta tempo de execução na ordem de g(n) = 100(log (n)) . Até qual valor de n compensa executar o algoritmo A?
Considerar log(n) como logaritmo na base 10 de n.

Answer 1

Resposta:

(B) 10

Explicação passo-a-passo:

F(n) = 10n e G(n)=100*log(n)

O problema pede para ser verificado até que valor de n compensa executar um algoritmo de ordem F(n) com relação a um algoritmo de ordem G(n), ou seja, até que valor de n temos: F(n) menor que ou igual a G(n).

É possível resolver substituindo cada valor em n. Fazendo isso, você obterá F(10) = G(10) = 100, F(20) é maior que G(20), F(50) é maior que G(50), F(93) é maior que G(93) e F(100) é maior que G(100).

Note que n é um número natural. Logo, o próximo valor será F(11), que é maior que G(11).

Faça o teste em uma calculadora científica ou algum software plotador de gráficos.