Esercizio 4

Esercizio 4   Siano $f(n)$ e $g(n)$ due funzioni asintoticamente non negative. Si assuma che $\lim_{n\mapsto \infty} \frac{f(n)}{g(n)}=5$. Dimostrare che $f(n) = O(g(n))$. Possiamo concludere che $f(n)=\Theta(g(n))$?

Supponiamo che sia

$$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \alpha,$$

per un qualche $\alpha>0.$ Allora, per la definizione di limite, dato un qualsiasi $\epsilon > 0$ possiamo trovare un $n_0$ a partire dal quale sia

$$\alpha - \epsilon \leq \frac{f(n)}{g(n)} \leq \alpha + \epsilon.$$

Scegliendo in particolare, ad esempio $\epsilon= \alpha/2,$ otteniamo

$$\frac{\alpha}{2} \leq \frac{f(n)}{g(n)} \leq \frac{3}{2}\alpha.$$

Supponiamo ora che $g(n) > 0$ a partire da un certo $n_1;$ sia $n_2 = \max(n_0, n_1).$ A partire da $n_2$ possiamo scrivere

$$\frac{\alpha}{2} g(n) \leq f(n) \leq \frac{3}{2}\alpha g(n)$$

il che è equivalente a dire che $f(n) \in \Theta(g(n)).$