Esercizio 1

Siano $f(n)$ e $g(n)$ due funzioni non negative e monotone non decrescenti. Dire quali delle seguenti affermazioni sono vere, fornendo un controesempio qualora non lo fossero:

1.

$(\min(f(n), g(n)) + \max(f(n), g(n))) \in \Theta (2 f(n) + 3 g(n));$

2.

$\Omega(\mid \! f(n)- g(n) \! \mid ) \cap O(f(n)+g(n)) = \Theta(f(n)+ g(n));$

3.

$f(n) \cdot f(n+2) \in O(f(n+1) \cdot f(n+1));$

4.

$4^{f(n)} + 4^{g(n)} \in O(2^{f(n)+ g(n)})$