Como podemos comparar taxas de crescimento de funções positivas quando x \rightarrow \infty ?

Passo 1

O problema é: dado duas funções positivas f(x) e g(x), queremos decidir qual cresce mais rápido quando x\to\infty. O assunto aqui é análise assintótica. Para isso vamos usar principalmente o limite do quociente f(x)/g(x) e as notações assintóticas O, o, \Theta e \sim.

Passo 2

Defina
L \;=\;\lim_{x\to\infty}\frac{f(x)}{g(x)}\,.
Então há três casos principais:
  • Se 0 < L < \infty, então f e g crescem na mesma ordem. Em notação:
f(x)=\Theta\bigl(g(x)\bigr).
E mais: se L=1, dizemos que f e g são equivalentes, escrevendo
f(x)\sim g(x).

Passo 3

Ainda partindo do mesmo limite L:
  • Se L=0, então f(x) cresce mais devagar que g(x). Escrevemos
f(x)=o\bigl(g(x)\bigr).
  • Se L=\infty, então f(x) cresce mais rápido que g(x), isto é
g(x)=o\bigl(f(x)\bigr).

Passo 4

As definições formais em termos de desigualdades (para x grande suficiente) são:
f(x)=O\bigl(g(x)\bigr)\quad\Longleftrightarrow\quad \exists\,C>0,\;x_0:\;f(x)\le C\,g(x)\quad\forall\,x>x_0,
f(x)=o\bigl(g(x)\bigr)\quad\Longleftrightarrow\quad \lim_{x\to\infty}\frac{f(x)}{g(x)}=0,
f(x)=\Theta\bigl(g(x)\bigr)\quad\Longleftrightarrow\quad f(x)=O\bigl(g(x)\bigr)\;\text{e}\;g(x)=O\bigl(f(x)\bigr).

Passo 5

Na prática costuma-se lembrar da hierarquia típica (quando x\to\infty e todas funções são positivas):
\underbrace{\log x}_{\text{mais lento}} \;\ll\; \underbrace{x^a}_{\text{polinomial}} \;\ll\; \underbrace{b^x}_{\text{exponencial}} \;\ll\; \underbrace{x!}_{\text{fatorial}}.
Para comparar duas delas, basta aplicar o teste do passo 2: calcular o limite do quociente.

Resposta

Para comparar o crescimento de f(x) e g(x) quando x\to\infty, calcule
L=\lim_{x\to\infty}\frac{f(x)}{g(x)}.
  • Se 0<L<\infty, então f(x)=\Theta(g(x)) (crescimento equivalente).
  • Se L=0, então f(x)=o(g(x)) ( f cresce mais devagar).
  • Se L=\infty, então g(x)=o(f(x)) ( f cresce mais rápido).
    Usamos também as notações O, o, \Theta e \sim para descrever formalmente essas ordens de crescimento.