Como provar ou refutar o seguinte: f(n) = O(g(n)) implica lg f(n) = O(lg g(n))

Como posso provar ou refutar o seguinte:

implies

?

Eu nunca gostei de usar igualdade junto com a notação big-O. It's usado nos artigos do wiki, mas usar igualdade em situações como esta é enganador. Quando você diz que uma coisa está em um conjunto determinado pela outra, você não deve't dizer que uma é igual ao conjunto determinado pela outra.

Mudando a notação, temos agora a questão

Como provar ou refutar o seguinte: se [matemática]f[/math] é [matemática]o(g)[/math] então [matemática]f[/math] é [matemática]O(g)[/math]?

Let's desembrulhe a declaração. Tire a conclusão do big-O. We'assumirá que ambas as funções são valorizadas positivamente, como sempre é o caso quando você'está olhando para o crescimento das funções. A declaração [matemática]f[/math] é [matemática]O(g)[/math] informalmente diz que [matemática]f[/math] não é muito maior que [matemática]g[/math]. Mais precisamente, ele diz que para grandes valores de [matemática]x[/math], [matemática]f(x)[/math] é limitado por alguns múltiplos de [matemática]g(x)[/math], ou seja, há algum número [matemática]M[/math] para que

[matemática]\qquad f(x)\leq M g(x)[/math]

para valores suficientemente grandes de [matemática]x[/math].

Agora pegue a hipótese do pouco-o. Para que [matemática]f[/math] seja [matemática]o(g)[/math], [matemática]f[/math] tem que ser muito menor que [matemática]g[/math] no seguinte sentido preciso: a razão [matemática]f(x)/g(x)[/math] aproxima-se de 0 como [matemática]x [/math] aproxima-se do infinito:

[math]\qquad\displaystyle\lim_{x)tofty}\frac{f(x)}{g(x)}=0[/math]

Now, é verdade que se essa razão se aproximar de 0 então [matemática]f[/math] é eventualmente limitada por um múltiplo de [matemática]g[/math]? Sim. Aqui's é uma prova.

Se a razão se aproximar de 0, isso significa que para qualquer positivo [matemática]{f(x)}epsilon[/math] há algum [matemática]N[/math] de modo que para grandes valores de [matemática]x[/math]

[matemática]\qquad\dfrac{f(x)}{g(x)}p>Take [matemática]{ /math]}epsilon=1[/math]. Então para grande [matemática]x[/math]

[matemática]\qquad \dfrac{f(x)}{g(x)}<1[/math]

Thus para grande [matemática]x[/math], nós temos [matemática]f(x)

Isso significa que ser pequeno-o de uma função é uma condição mais forte do que ser grande-O de uma função.