Repita o exercício 23, para as funções:

n ; raiz(n) log_2(n) ; (log_2(n))^2

Passo 1

Galera, queremos saber quais dos algoritmos é mais eficiente. Portanto, estamos diante de uma questão sobre taxas relativas de crescimento. Vamos calcular os limites??

lim n → ∞ ⁡ ( log 2 ⁡ n ) 2 n =   l i m n → ∞   ln ⁡ n ln ⁡ 2   2 n =   l i m n → ∞   ( ln ⁡ n   ) 2 n   ( ln ⁡ 2 )   2

= n   l i m n → ∞   2 ( ln ⁡ n ) 1 n ( ln ⁡ 2 ) 2 =   2 ( ln ⁡ 2 ) 2 l i m n → ∞   ln ⁡ n   n

= 2 ( ln ⁡ 2 ) 2 l i m n → ∞ 1 n 1 = 0

Assim, ( log 2 ⁡ n ) 2 cresce mais lentamente que n . Agora, vamos verificar para a função que ainda falta.

l i m n → ∞   ( log 2 ⁡ n ) 2 n log 2 ⁡ n =   l i m n → ∞   log 2 ⁡ n n =   l i m n → ∞   ln ⁡ n ln ⁡ 2   n 1 2 = 1 ln ⁡ 2   l i m n → ∞   ln ⁡ n   n 1 2

= 1 ln ⁡ 2     l i m n → ∞   1 n 1 2 n - 1 2 = 2 ln ⁡ 2 l i m n → ∞ 1 n 1 2 = 0

( log 2 ⁡ n ) 2 cresce mais lentamente que n log 2 ⁡ n

Assim, concluímos que o algoritmo mais eficiente é y = n

Passo 2

A imagem gráfica será:

Resposta

  1. o algoritmo mais eficiente é y = n
  2. Gráfico
Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados