Funzioni elementari

• $$\log n=O(n)$$

  Infatti se $\log n=\ln n$, si sa che $\ln n\le n-1\le n$ perchè $n-1$ è la tangente di $\ln n$ su $n=1$.

  Analoghe sono le altre basi di $\log$.

• $$n\log n=O(n^2)$$

  Sapendo che $\log n\le n$ per la precedente dimostrazione, anche $n\cdot \log n\le n\cdot n$.

• $$n!=O(n^n)$$

  Infatti $n!=\underset{n}{\underbrace{\stackrel{\le n}{1}\cdot \stackrel{\le n}{2}\cdot ...\cdot \stackrel{\le n}{n}}}\le \underset{n}{\underbrace{n\cdot n\cdot ...\cdot n}}$.

• $$n!=\Omega (2^n)$$

  Per cui $n!=1\cdot \stackrel{\ge 2}{2}\cdot ...\cdot \stackrel{\ge 2}{n}\ge 1\cdot 2\cdot ...\cdot 2=2^{n-1}$, di conseguenza $n!\ge c\cdot 2^n=2^{n-1}$ se $c=\frac{1}{2}$.

• $$\log n!=O(n\log n)$$

  Sapendo che $n!\le n^n$ per le precedenti dimostrazioni, allora $\log n!\le \log n^n=n\log n$

• $$\sqrt{n}=O(n)$$

  Infatti se $n\le n^2$, allora $\sqrt{n}\le n$.

• $$\log n=O(\sqrt{n})$$

  Infatti $\underset{n\to +\infty }{\lim }\frac{\log n}{\sqrt{n}}\stackrel{\mathcal{H}}{\underset{\left[\frac{0}{0}\right]}{=}}\underset{n\to +\infty }{\lim }\frac{\frac{1}{n}}{\frac{1}{2}{n}^{-\frac{1}{2}}}=0$, per cui $\log n\in o(\sqrt{n})\subset O(\sqrt{n})$.

Tra cui, i casi meno frequenti:

• $$(1+\sin n)n=O(n)$$

  Dato che $0\le 1+\sin n\le 2\iff 0\le (1+\sin n)\le 2n$, è valido per $c=2$ anche se $\nexists \underset{n\to +\infty }{\lim }\frac{(1+\sin n)n}{n}$.