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 quocientef(x)/g(x) e as notações assintóticasO, 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:
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.
Cálculo - Thomas - Vol 1 - 11ª Edição - Capítulo 7.Questões de Revisão - Ex. 6