Teorija 3 - Asimptotična zahtevnost

Naloga 1

Z uporabo definicije pokaži, da je   \( f(x) = \Theta(g(x)) \), če je\( f(x) = 3 x^2 + 7 x -1 \) in \(g(x)\) enako \(x^2 \). 

Naloga 2

Z uporabo limit pokaži v kakšnem odnosu je \( f(x) = 3 x^2 + 7 x - 1 \) , če je \( g(x) \) enako  \(x^2 \) .

Naloga 3

Z uporabo limit pokaži, da so polinomi počasnejši od eksponentnih funkcij.

Naloga 4

Uredi po vrsti tako, da bo veljalo \(f_i=\Omega(f_{i+1})\):

\( 2^{2^n}, \ \ \ n^2, \ \ \ \lg n, \ \ \ (3/2)^n, \ \ \ \lg^2 n, \ \ \ n!, \ \ \ \lg \lg n, \ \ \ e^n, \ \ \ n \lg n, \)

\( n 2^n, \ \ \ n^3, \ \ \ 2^n, \ \ \ n, \ \ \ 1, \ \ \ (n+1)!, \ \ \ n \log n, \ \ \ 2^{2^{n+1}}, 42, \ \ \ n^n, \ \ \ \sqrt{n} \)