soluzione formale

$$f_1(n) <_1 f_8(n) <_2 f_3(n) <_3 f_4(n) <_4 f_5(n)=_5 f_7(n) <_6 f_6(n) <_7 f_{10}(n) <_8 f_2(n) <_9 f_9(n).$$

Dimostro $f_1(n) <_1 f_8(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_1(n)}{f_8(n)}= \lim_{n \right... ...\frac{2^{\log_2 n}}{4^{\log_2 n}}= \lim_{n \rightarrow \infty} \frac{n}{n^2}=0$$

Dimostro $f_8(n) <_2 f_3(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_8(n)}{f_3(n)}= \lim_{n \right... ...row \infty} \frac{4^{\log_2 n}}{{\frac{(\log_2 n)}{2}}^{\frac{(\log_2 n)}{2}}}$$

Dove abbiamo usato il fatto che $n!\geq \frac{n}{2}^{\frac{n}{2}}$ per $n>0$. Pertanto

$$\lim_{n \rightarrow \infty} \frac{f_8(n)}{f_3(n)}= \lim_{n \rightarrow \infty} \left( \frac{32}{\log_2 n} \right)^ {\frac{\log_2 n}{2}}= 0$$

Dimostro $f_3(n) <_3 f_4(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_3(n)}{f_4(n)}= \lim_{n \right... ...n}}\leq \lim_{n \rightarrow \infty} \frac{(\log_2 n)^{\log_2 n}}{n^{\log_2 n}}$$

Dove abbiamo usato il fatto che $n!\leq n^n$ per $n>0$. Pertanto

$$\lim_{n \rightarrow \infty} \frac{f_3(n)}{f_4(n)}\leq \lim_{n \ri... ...n)^{\log_2 n}}{n^{\log_2 n}} =\left( \frac{\log_2 n}{n} \right)^{\log_2 n}= 0.$$

Dimostro $f_4(n) <_4 f_5(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_4(n)}{f_5(n)}= \lim_{n \right... ... n - n} = 2^{\lim_{n \rightarrow \infty} (\log^2_2 n - n)} = 2^{- \infty} = 0.$$

Dimostro $f_5(n)=_5 f_7(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_5(n)}{f_7(n)}= \lim_{n \rightarrow \infty} \frac{2^n}{2^{n+1}}= \frac{1}{2} > 0.$$

Dimostro $f_7(n) <_6 f_6(n)$:

$$\lim_{n \rightarrow \infty} \frac{2^{n+1}}{4^n}= \lim_{n \rightar... ...2 \lim_{n \rightarrow \infty} \left( \frac{1}{2} \right)^n= 2 \cdot 0 = 0.$$

Dimostro $f_6(n) <_7 f_{10}(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_6(n)}{f_{10}(n)}= \lim_{n \ri... ...00}}= \lim_{n \rightarrow \infty} \left( \frac{4^{100}}{n} \right)^{n/100}= 0.$$

Dimostro $f_{10}(n) <_8 f_2(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_{10}(n)}{f_2(n)}= \lim_{n \ri... ...arrow \infty} \frac{n^{n/100}}{\left( \frac{49}{50} n \right)^{\frac{n}{50}}}$$

Dove abbiamo usato il fatto che

$$n! \geq n(n-1) \cdots \left( n- \frac{n}{50} \right) \geq \left(n... ...n}{50} \right)^{\frac{n}{50}} = \left(\frac{49}{50} n \right)^{\frac{n}{50}} =$$

Pertanto

$$\lim_{n \rightarrow \infty} \frac{f_{10}(n)}{f_2(n)} \leq \lim_{... ...n \rightarrow \infty} \left( \frac{50}{49 \sqrt{n}} \right)^{\frac{n}{50}} = 0$$

Dimostro $f_2(n) <_9 f_9(n)$:

$$\lim_{n \rightarrow \infty} \frac{f_2(n)}{f_9(n)}= \lim_{n \right... ...rrow \infty} \frac{n!}{n \cdot n!}= \lim_{n \rightarrow \infty} \frac{1}{n}= 0$$