Descreva exemplos de crescimento não clássico.

Passo 1

Você perguntou: “Descreva exemplos de crescimento não clássico.”
Vou interpretar isso como pedir exemplos de funções (ou leis de crescimento) cujo comportamento para x\to\infty foge do padrão mais comum (por exemplo: simples polinomial ou simples exponencial) e também explicações didáticas de por que cada exemplo é considerado “não clássico” e como analisá-lo.
Informações que vou usar e entregar: uma definição clara de como comparamos crescimentos assintóticos, uma lista de exemplos variados de crescimento não clássico, e para cada exemplo uma explicação passo a passo de como entender/medir esse crescimento (com limites, comparação assintótica, e ferramentas como L’Hôpital e Stirling quando necessário).

Passo 2

O que significa “comparar crescimentos”? Vou te ensinar a linguagem mínima que precisa para entender as comparações:
  • Dizemos que f(x) cresce menos que g(x) quando
\lim_{x\to\infty}\frac{f(x)}{g(x)}=0.
Isso se escreve f(x)=o(g(x)). Aqui f e g são funções reais positivas para x grande.
  • Dizemos que f e g têm o mesmo crescimento assintótico quando
\lim_{x\to\infty}\frac{f(x)}{g(x)}=c\in(0,\infty),
ou seja, f(x)\sim c\,g(x).
  • A notação f(x)=O(g(x)) significa que existe constante C e x_0 tais que |f(x)|\le C|g(x)| para x\ge x_0. Isso é útil para comparações rápidas.
    Esses conceitos são as “ferramentas” que vamos usar para dizer por que um exemplo é mais lento ou mais rápido que outro.

Passo 3

Rápido lembrete do “clássico” para termos ponto de referência (não resolvo nada, só marco a escala):
  • Crescimentos muito lentos: \log x,\\ \log\log x.
  • Crescimentos polinomiais: x^\alpha com \alpha>0.
  • Crescimentos exponenciais: e^{cx} com c>0.
  • Crescimentos superexponenciais: iterações de exponencial \exp(\exp(x)), etc.
    “Não clássico” será qualquer exemplo que não caiba bem nessa hierarquia simples (por exemplo: mistura de fatores, oscilações, crescimento irregular, crescimento subexponencial mas maior que todo polinômio, etc.). Agora vamos aos exemplos concretos e à didática de cada um.

Passo 4

Exemplo 1 — Funções lentamente variáveis: \log x e \log\log x.
Por que são “não clássicas”? Porque crescem mais devagar que qualquer potência positiva de x: para todo \epsilon>0,
\lim_{x\to\infty}\frac{\log x}{x^\epsilon}=0.
Como ver isso na prova (método): aplicar L’Hôpital à \lim_{x\to\infty}\frac{\log x}{x^\epsilon}. Veja:
\lim_{x\to\infty}\frac{\log x}{x^\epsilon} = \lim_{x\to\infty}\frac{1/x}{\epsilon x^{\epsilon-1}} = \lim_{x\to\infty}\frac{1}{\epsilon x^\epsilon}=0.
Isto ensina: logaritmo é “muito menor” que qualquer polinômio; \log\log x é ainda mais lento.

Passo 5

Exemplo 2 — Funções polinomiais com fator log: x^\alpha\log x (com \alpha>0).
Por que é interessante? Porque representam crescimento “próximo” ao polinomial mas ligeiramente maior. Comparações úteis:
  • Se \beta>\alpha então x^\alpha\log x=o(x^\beta). Em prova: basta dividir e usar que \log x=o(x^{\beta-\alpha}).
  • x^\alpha\log x é o(e^{\delta x}) para todo \delta>0 (ou seja, ainda menor que exponencial).
    Essa família aparece muito em estimativas finas (por ex. em teoria de números ou análise assintótica).

Passo 6

Exemplo 3 — Subexponenciais: \exp(\sqrt{x}), \exp(x^\gamma) com 0<\gamma<1.
Por que são “não clássicas”? Estão entre polinômios e exponenciais clássicas e^{cx}: crescem mais rápido que todo polinômio, mas mais devagar que e^{cx} para qualquer c>0. Demonstração típica: para qualquer n>0,
\lim_{x\to\infty}\frac{x^n}{\exp(\sqrt{x})}=0,
pois o log do denominador cresce como \sqrt{x} que domina \log x^n=n\log x para x grande. E para qualquer c>0,
\lim_{x\to\infty}\frac{\exp(\sqrt{x})}{e^{c x}}=0,
pois \sqrt{x}-c x\to -\infty. Em provas, usar o comparador no expoente é a forma direta: comparar os expoentes.

Passo 7

Exemplo 4 — Superexponenciais/iterações: \exp(\exp(x)), ou em notação e^{e^x}.
Por que é “não clássico”? Porque cresce bem mais rápido que qualquer exponencial simples e^{cx}. Em provas, para comparar e^{e^x} e e^{cx}, olhe para o quociente:
\frac{e^{e^x}}{e^{cx}}=e^{e^x-cx}\to\infty,
pois e^x domina linearmente cx. Essas funções aparecem em problemas de complexidade extrema e em algumas séries singulares.

Passo 8

Exemplo 5 — Fatorial e \Gamma: n! ou \Gamma(x+1) para x contínuo.
Por que é especial? n! cresce mais rápido que a^n para qualquer a>0? Na verdade, n! cresce mais rápido que c^n somente se compararmos a taxa por termos (mas n! é superexponencial no sentido de n!\sim \sqrt{2\pi n}(n/e)^n — Stirling). Ferramenta de prova (Stirling):
n! \sim \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^n.
Isso te dá a ordem: (n/e)^n é exponencial em n\log n, muito maior que a^n para base fixa a. Em provas envolvendo somatórios com n! é comum aplicar essa aproximação.

Passo 9

Exemplo 6 — Oscilações multiplicativas: x^{\sin x} ou x(1+\sin x).
Por que é não clássico? Porque não é monotônico: a função alterna entre ordens diferentes. Por exemplo, x^{\sin x} toma valores entre x^{-1} e x (pois \sin x\in[-1,1]). Assim não existe um único “taxa” de crescimento — o comportamento depende de subsequências. Como analisar numa prova: mostre que existem subsequências x_k com \sin x_k\to 1 onde x^{\sin x}\sim x, e outras com \sin x_k\to -1 onde x^{\sin x}\sim x^{-1}. Isso mostra que limites simples podem não existir e atenção ao falar de crescimento assintótico.

Passo 10

Exemplo 7 — Funções com crescimento irregular: f(x)=\exp(x)\cdot(1+\sin(e^x)).
Por que é curioso? O fator oscilatório \sin(e^x) faz com que f(x) oscile entre cerca de 0 e 2e^x multiplicativamente. Embora em escala geral o comportamento seja exponencial, localmente a função pode ficar próxima de zero (quando \sin(e^x)\approx -1). Em provas, isso mostra que ser "da ordem de e^x" não implica monotonicidade ou que todos os limites subsequenciais existam.

Passo 11

Exemplo 8 — Funções regularmente e lentamente variáveis (conceito importante):
  • Uma função L(x) é lentamente variável se, para todo t>0,
\lim_{x\to\infty}\frac{L(tx)}{L(x)}=1.
Ex.: L(x)=\log x, L(x)=\log\log x.
  • Uma função f é regularmente variável de índice \alpha se
f(x)=x^\alpha L(x),
com L lentamente variável. Ex.: x^\alpha\log x.
Por que serve? Esse conceito ordena muitos crescimentos “não clássicos” e é muito útil em provas de análise e probabilidade assintótica (caudas de distribuição, etc.). A técnica é fatorar o crescimento polinomial dominante e estudar o fator lento L(x).

Passo 12

Exemplo 9 — Crescimento estocástico/esperado: processos de ramificação ou crescimento aleatório.
Aqui “não clássico” significa que a taxa média pode ser exponencial, mas trajetórias individuais podem ter comportamento muito diferente (extinção, explosão em subamostras). Ferramenta: trabalhar com esperança \mathbb{E}[X_n] e variância, e distinguir crescimento em média de crescimento quase certo. Embora este tópico seja mais de probabilidade, é um exemplo concreto de crescimento que não se encaixa em uma simples curva determinística.

Passo 13

Resumo prático para aplicar na prova (como decidir que tipo é):
  1. Calcule \lim_{x\to\infty}\frac{\log f(x)}{\log x}. Se for finito e positivo, f é polinomial em ordem. Se esse limite é infinito, costuma ser superpolinomial.
  2. Compare expoentes: olhar para o expoente em funções do tipo e^{g(x)}. Se g(x)=o(x) então e^{g(x)} é subexponencial frente a e^{cx}.
  3. Procure fatores lentamente variáveis L(x) (logs, log-logs) que alteram a ordem só levemente.
  4. Verifique monotonicidade/oscilações: se há seno/cosseno dentro de expoentes ou potências, cuidado: pode não existir limite único.
    Esses passos te ajudam a classificar rápido e escrever justificativas curtas e seguras na prova.

Resposta

\log x \n
\log\log x \n
x^\alpha\log x (com \alpha>0) \n
\exp(\sqrt{x}) e mais geral \exp(x^\gamma) com 0<\gamma<1 \n
\exp(\exp(x)) (iterações de exponencial) \n
n! (ou \Gamma(x+1), com aproximação de Stirling) \n
x^{\sin x} e x(1+\sin x) (oscilações multiplicativas) \n
\exp(x)\cdot(1+\sin(e^x)) (exponencial com oscilação) \n
funções regularmente variáveis f(x)=x^\alpha L(x) com L lentamente variável (ex.: x^\alpha\log x) \n
crescimentos estocásticos (ex.: processos de ramificação, onde trajetórias individuais podem divergir do crescimento médio)

Exercícios relacionados