comprensione

Essendo $f(n) \in O(g(n))$, sappiamo che $\exists k>0, \exists \bar{n}_0$ tali che $\forall n \geq \bar{n}_0, 0 \leq f(n) \leq k g(n)$. Segue per le proprietà delle disequazioni che

$$5 \cdot 0 + 2 g(n) \leq 5 f(n) + 2 g(n) \leq 5k g(n) + 2 g(n).$$

Ricordiamo che

$$\Theta(g(n)) = \{ h(n) \mid \exists \alpha >0 \exists \beta > ... ... n_1 \mid \forall n \geq n_1, 0 \leq \alpha g(n) \leq f(n) \leq \beta g(n) \}$$

Ma allora possiamo prendere $\alpha= 2, \beta= 5k + 2, n_1 = n_0$ e l'appartenenza di $h(n)= 5 f(n) + 2 g(n)$ a $\Theta(g(n))$ è dimostrata. Si noti come, per la limitazione inferiore, abbiamo usato in maniera essenziale la non negatività asintotica di $f(n)$.

Abbiamo detto infatti che $f(n), g(n) \geq 0$ per ogni $n\geq n_0$. (D'altronde $f(n) = X(g(n))$, qualunque sia il simbolo $X$ tra quelli da noi visti, implica che $f(n)$ e $g(n)$ sono definitivamente non negative).