comprensione

Riscriviamole intanto nei modi più convenienti per il confronto. Di quasi tutte diamo anche il logaritmo in base due, poichè per ordinare molte di esse è sufficiente confrontarne i logaritmi. Sia infatti $s_1(n)= 2^{t_1(n)}$ e $s_2(n)= 2^{t_2(n)}.$ Abbiamo allora i fatti seguenti:

a)

se $t_1(n) \in \Theta(t_2(n))$ (e, quindi, anche viceversa) in genere non si può dire nulla del confronto tra le funzioni originarie. Ma se, ad esempio, $t_1(n) - t_2(n) \rightarrow \infty,$ allora $s_2(n) \in o(s_1(n)).$

b)

supponiamo che si abbia $t_1(n) \geq \alpha, t_2(n) \geq \alpha$ per un certo $\alpha>0.$ Allora, se ad esempio, $t_2(n) \in o(t_1(n)),$ segue $s_2(n) \in o(s_1(n)).$

Dimostriamo a): se $t_1(n) - t_2(n) \rightarrow \infty,$ allora

$$\frac{s_1(n)}{s_2(n)} = 2^{t_1(n) - t_2(n)} \rightarrow \infty.$$

Per dimostrare b), notiamo che $t_2(n) \in o(t_1(n))$ è equivalente a dire

$$\lim_{n \rightarrow \infty} \frac{t_1(n)}{t_2(n)} = \infty$$

da cui anche

$$\lim_{n \rightarrow \infty} \frac{t_1(n)- t_2(n)}{t_2(n)} = \infty.$$

Dato che, definitivamente, $t_2(n) \geq \alpha,$ abbiamo

$$\lim_{n \rightarrow \infty} t_1(n)- t_2(n) = \infty$$

da cui la tesi segue per il punto a).

Veniamo alle dieci funzioni. Per i fattoriali, sfruttiamo il fatto che $\log(k!) \in \Theta(k \log k).$

$$f_1(n) = 2^{\log_2 n} = n = 2^{\Theta(\log n)}$$

$$f_2(n) = n ! = 2^{\Theta (n \log n))}$$

$$f_3(n) = (\log_2 n) ! = 2^{\Theta(\log n \log \log n)}$$

$$f_4(n) = n^{\log_2 n} = (2^{\log_2 n})^{\log_2 n} = 2^{\Theta(\log^2 n)}$$

$$f_5(n) = 2^n$$

$$f_6(n) = 4^n = 2^{2n}$$

$$f_7(n) = 2^{n+1}= 2 \cdot 2^n$$

$$f_8(n) = 4^{\log_2 n}= (2^2)^{\log_2 n}= (2^{\log_2 n})^2 = n^2 = 2^{\Theta(\log n)}$$

$$f_9(n) = (n+1)! - n! = [(n+1)-1] n! = n \cdot n! = 2^{\Theta(n \log n)}$$

$$f_{10}(n) = n^{n/100} = 2^{\frac{n \log_2 n}{100}}$$

Le due funzioni con logaritmo minore sono $f_1(n)$ e $f_8(n);$ chiaramente, $f_1(n) < f_8 (n).$ Usiamo la notazione del confronto fra numeri seguendo l'ovvia analogia. Subito dopo vengono $f_3(n)$ e $f_4(n).$ Seguono le funzioni che hanno logaritmo lineare; vediamo che $f_5(n)= f_7(n) < f_6(n).$ Vi sono poi tre funzioni il coi logaritmo è $\Theta(n \log n).$ Se è chiaro che $f_2(n) < f_9(n),$ bisogna classificare $f_{10}(n).$ Mostriamo che essa cresce meno del fattoriale. Ricordiamo che $n! \geq (\frac{n}{2})^{\frac{n}{2}}$ da cui

$$\log_2 (n!) \geq \frac{n}{2} \log_2 n - \frac{n}{2}$$

e

$$\log_2 (f_2(n)) - log_2 (f_{10}(n)) \geq \frac{49}{100} n \log_2 n - \frac{n}{2}$$

per cui possiamo sfruttare il punto b) di sopra. Abbiamo in defnitiva

$$f_1(n) < f_8(n) < f_3(n) < f_4(n) < f_5(n)= f_7(n) < f_6(n) < f_{10}(n) < f_2(n) < f_9(n).$$