comprensione

Scriviamo le definizioni di $o(g(n))$ e di $\omega(f(n))$:

$$o(g(n)) = \{ f(n) \mid \forall k>0 \exists n_0 \mid \forall n \geq n_0, 0 \leq f(n) \leq k g(n) \}$$

$$\omega(f(n)) = \{ g(n) \mid \forall h>0 \exists n_1 \mid \forall n \geq n_1, g(n) \geq h f(n) \geq 0 \}$$

Abbiamo già sistemato i nomi del generico elemento di $o(g(n))$ e di $\omega(f(n))$ in modo da attagliarsi al meglio al nostro problema; l'unica difficoltà che ci rimane è di mostrare che le due condizioni sono equivalenti. Ma ciò segue dall'arbitrarietà di $k$ e di $h,$ ad esempio come $h$ nella seconda condizione possiamo prendere $1/k,$ al che essa diventa formalmente uguale alla prima condizione.