Enumere as funções abaixo da menor para a maior ordem de crescimento. Caso duas ou mais tenham a mesma ordem, indique-as.
ccc n & 2^n & n lg n n-n^3+7 n^5 & lg n & raizn n^2+lg n & n^2 & 2^n-1 n^3 & (lg n)^2 & n!

Passo 1

Beleza, vamos começar resumindo o que a questão está pedindo. A gente tem uma lista de funções matemáticas e precisa organizá-las da menor para a maior ordem de crescimento. Isso significa que vamos ver quais funções crescem mais rápido conforme $ n $ aumenta. Para resolver isso, vamos usar conceitos de análise assintótica e ordem de crescimento. Vamos precisar comparar cada função e entender como elas se comportam quando $ n $ fica muito grande.

Passo 2

Vamos listar todas as funções que temos:
  1. $ n $
  2. $ 2^{n} $
  3. $ n \lg n $ (onde $ \lg n $ é logaritmo na base 2)
  4. $ n - n^{3} + 7n^{5} $
  5. $ \lg n $
  6. $ \sqrt{n} $
  7. $ n^{2} + \lg n $
  8. $ n^{2} $
  9. $ 2^{n-1} $
  10. $ n^{3} $
  11. $ (\lg n)^{2} $
  12. $ n! $

Passo 3

Vamos começar identificando a ordem de crescimento de cada função:
  1. Logarítmicas:
    • $ \lg n $
    • $ (\lg n)^{2} $
  2. Polinomiais:
    • $ \sqrt{n} = n^{0.5} $
    • $ n $
    • $ n \lg n $
    • $ n^{2} $
    • $ n^{2} + \lg n $
    • $ n^{3} $
    • $ n - n^{3} + 7n^{5} $ (a função de maior grau domina, então $ 7n^{5} $)
  3. Exponenciais:
    • $ 2^{n} $
    • $ 2^{n-1} $ (igual a $ 2^{n} / 2 $, que é da mesma ordem que $ 2^{n} $)
  4. Fatorial:
    • $ n! $

Passo 4

Agora, vamos organizar essas funções do menor para o maior crescimento:
  • Menor crescimento:
    1. $ \lg n $ (logarítmica)
    2. $ (\lg n)^{2} $ (logarítmica quadrática)
    3. $ \sqrt{n} $ (raiz quadrada, que é $ n^{0.5} $)
  • Crescimento linear e superlinear:
    4. $ n $ (linear)
    5. $ n \lg n $ (linear com logaritmo)
  • Crescimento quadrático:
    6. $ n^{2} $ e $ n^{2} + \lg n $ (ambas são da ordem $ n^{2} $, já que $ \lg n $ é insignificante em comparação)
  • Crescimento cúbico e maior:
    7. $ n^{3} $
    8. $ n - n^{3} + 7n^{5} $ (dominado por $ 7n^{5} $, que é $ n^{5} $)
  • Crescimento exponencial:
    9. $ 2^{n} $ e $ 2^{n-1} $ (ambas são da ordem $ 2^{n} $)
  • Maior crescimento:
    10. $ n! $ (fatorial, cresce mais rápido que exponenciais)

Resposta

Organizando as funções da menor para a maior ordem de crescimento:
  1. $ \lg n $
  2. $ (\lg n)^{2} $
  3. $ \sqrt{n} $
  4. $ n $
  5. $ n \lg n $
  6. $ n^{2} $ e $ n^{2} + \lg n $
  7. $ n^{3} $
  8. $ n - n^{3} + 7n^{5} $
  9. $ 2^{n} $ e $ 2^{n-1} $
  10. $ n! $

Exercícios relacionados