Come dimostrare o confutare quanto segue: f(n) = O(g(n)) implica lg f(n) = O(lg g(n))

Come posso provare o confutare quanto segue:

implica

?

Non mi è mai piaciuto usare l'uguaglianza insieme alla notazione big-O. È usata negli articoli del wiki, ma usare l'uguaglianza in situazioni come questa è fuorviante. Quando si dice che una cosa è in un insieme determinato dall'altra, non si dovrebbe dire che l'una è uguale all'insieme determinato dall'altra.

Cambiando la notazione, ora abbiamo la domanda

Come posso provare o confutare quanto segue: se [math]f[/math] è [math]o(g)[/math] allora [math]f[/math] è [math]\mathcal O(g)[/math]? Prendiamo la conclusione big-O. Assumiamo che entrambe le funzioni siano valutate positivamente, come è sempre il caso quando si guarda alla crescita delle funzioni. L'affermazione [math]f[/math] è [math]\mathcal O(g)[/math] dice informalmente che [math]f[/math] non è molto più grande di [math]g[/math]. Più precisamente, dice che per grandi valori di [math]x[/math], [math]f(x)[/math] è limitata da qualche multiplo di [math]g(x)[/math], cioè, c'è qualche numero [math]M[/math] in modo che

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

per valori sufficientemente grandi di [math]x[/math].

Prendiamo ora l'ipotesi little-o. Perché [math]f[/math] sia [math]o(g)[/math], [math]f[/math] deve essere molto più piccolo di [math]g[/math] nel seguente preciso senso: il rapporto [math]f(x)/g(x)[/math] si avvicina a 0 man mano che [math]x[/math] si avvicina all'infinito:

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

Ora, è vero che se questo rapporto si avvicina a 0 allora [math]f[/math] è alla fine limitato da un multiplo di [math]g[/math]? Sì. Ecco una prova.

Se il rapporto si avvicina a 0, ciò significa che per qualsiasi [math]\epsilon[/math] positivo esiste un certo [math]N[/math] in modo che per grandi valori di [math]x[/math]

[math]\qquad\dfrac{f(x)}{g(x)}<\epsilon[/math]

Prendiamo [math]\epsilon=1[/math]. Allora per grandi [math]x[/math]

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

Quindi per grandi [math]x[/math], abbiamo [math]f(x)

Questo significa che essere little-o di una funzione è una condizione più forte che essere big-o di una funzione.