Enunciado

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

n ; sqrt(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??

underset(n -> oo)(lim) (( log_2 n )^2)/(n) = underset(n -> oo)(l i m) (((ln n)/(ln 2))^2)/(n) = underset(n -> oo)(l i m) (( ln n )^2)/(n ( ln 2 )^2)

= n underset(n -> oo)(l i m) (2 ( ln n ) (1)/(n))/(( ln 2 )^2) = (2)/(( ln 2 )^2) underset(n -> oo)(l i m) (ln n)/(n)

= (2)/(( ln 2 )^2) underset(n -> oo)(l i m) ((1)/(n))/(1) = 0

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

underset(n -> oo)(l i m) (( log_2 n )^2)/(sqrt(n) log_2 n) = underset(n -> oo)(l i m) (log_2 n)/(sqrt(n)) = underset(n -> oo)(l i m) (((ln n)/(ln 2)))/(n^((1)/(2))) = (1)/(ln 2) underset(n -> oo)(l i m) (ln n)/(n^((1)/(2)))

= (1)/(ln 2) underset(n -> oo)(l i m) ((1)/(n))/((1)/(2) n^(- (1)/(2))) = (2)/(ln 2) underset(n -> oo)(l i m) (1)/(n^((1)/(2))) = 0

( log_2 n )^2 cresce mais lentamente que sqrt(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

59. Use a Definição 4.1.1 para provar que:b) Se f for decrescente nos intervalos a ,c e c ,b , então f será decrescente em a ,b .
Use a parte b) do Exercício 59 para mostrar que f x = cos ⁡ x - x é decrescente no intervalo - ∞ ,+ ∞ .
55. Em cada parte, encontre funções f e g que sejam crescentes em - ∞ ,+ ∞ e com as quais f - g tem a propriedade indicada.b) f - g é constante em - ∞ ,+ ∞ .
59. Use a Definição 4.1.1 para provar que:a) Se f for crescente nos intervalos a ,c e c ,b , então f será crescente em a ,b .
56. Em cada parte, encontre funções f e g que sejam positivas e crescentes em - ∞ ,+ ∞ e com as quais f g tem a propriedade indicada.a) f g é decrescente em - ∞ ,+ ∞ .