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)})$

Le risposte, punto per punto, sono le seguenti:

1.

Notare che $(\min(f(n), g(n)) + \max(f(n), g(n))) = f(n) + g(n).$ Abbiamo poi

$$\frac{1}{3} (2 f(n) + 3 g(n)) \leq f(n) + g(n) \leq \frac{1}{2} (2 f(n) + 3 g(n)),$$

quindi l'affermazione è vera e le costanti nascoste dalla notazione theta sono $\frac{1}{3}$ e $\frac{1}{2}.$

2.

Falso, come si vede prendendo $g(n)= f(n),$ dove $f(n)$ è una qualsiasi funzione non costante. Siccome allora $\Omega(\mid \! f(n)- g(n) \! \mid )$ è l'insieme di tutte le funzioni definitivamente non negative (cioè, di tutte le funzioni alle quali le nostre notazioni si applicano), il membro sinistro è semplicemente $O(f(n)+g(n))$, che sappiamo essere diverso da $\Theta(f(n)+ g(n)).$ Concretamente, prendendo $f(n)= g(n)= n^2,$ allora $h(n)= n$ appartiene al membro sinistro ma non a quello destro.

L'uguaglianza sussiste invece con l'ipotesi aggiuntiva $g(n)= o(f(n)).$

3.

Con una traslazione di indice, possiamo mettere il quesito nella forma $f(n-1) \cdot f(n+1) \in O(f(n) \cdot f(n));$

Qualche tentativo: prima con una funzione polinomiale, e.g. $f(n)= n^k.$ Abbiamo

$$\frac{(n-1)^k (n+1)^k}{n^k n^k} = \left(\frac{n^2 - 1}{n^2}^k \right) < 1$$

per cui la proposizione è in questo caso vera.

Indi con una funzione esponenziale: $f(n)= k^n$

$$\frac{k^{n-1} k^{n+1}}{k^n k^n} = 1.$$

per cui la proposizione è ancora vera.

Anche con $f(n)= k^{n^2}$

$$\frac{k^{{(n-1)}^2} k^{{(n+1)}^2}}{k^{n^2} k^{n^2}} = k^{{(n-1)}^2 + {(n+1)}^2 - 2 n^2}= k^2$$

per cui la proposizione è ancora vera.

Con $f(n)= k^{n^3},$ tuttavia, le cose cambiano: ad es. con $f(n)= k^{n^3}$ si ha

$$\frac{k^{(n-1)^3} k^{(n+1)^3}}{k^{n^3} k^{n^3}} = k^{(n-1)^3 + (n+1)^3 - 2 n^3} = k^{6n},$$

rapporto che tende a infinito, per cui la proposizione è falsa.

4.

Falso, come si vede prendendo ad esempio $f(n)= 1$ (ricordando che deve essere positiva) e $g(n)=n$. Notare che basterebbe anche prendere una $g(n)$ crescente in modo molto piú debole, come $g(n)= \log n$.