Matematyka dyskretna 1/Test 9: Asymptotyka

Funkcja $n^2\lg n+\frac{n^2\sqrt{n}}{\lg n}$ jest:

$\mathrm{\Theta }(n^2\lg n)$ Źle

$O(n^2\lg n)$ Źle

$\mathrm{\Theta }{n}^2\sqrt{n}$ Źle

$O(\frac{n^2\sqrt{n}}{\lg n})$ Dobrze

Funkcja $\frac{n^9}{{\lg }^{10}n}$ jest:

$O(n^{\frac{9}{10}})$ Źle

$O(n)$ Źle

$O(n^9)$ Dobrze

$\mathrm{\Omega }({\lg }^{10}n)$ Dobrze

Dla $f(n)=2^{\lg n+1}$ oraz $g(n)=\lg 2n-1$ zachodzi:

$f(x)=\omega (g(x))$ Źle

$f(x)=\mathrm{\Omega }(g(x))$ Dobrze

$f(x)=\mathrm{\Theta }(g(x))$ Dobrze

$f(x)=O(g(x))$ Dobrze

$f(x)=o(g(x))$ Źle

Dowolny wielomian $k$-tego stopnia jest:}

$\mathrm{\Omega }(n^k)$ Dobrze

$\mathrm{\Theta }(n^k)$ Dobrze

$O(n^k)$ Dobrze

$o(n^{k+\epsilon })$ dla dowolnego $\epsilon >0$ Dobrze

Dla $f(n)=\frac{\lg n}{n}$ oraz $g(n)=\frac{1}{\sqrt{n}}$ zachodzi:

$f(x)=\omega (g(x))$ Źle

$f(x)=\mathrm{\Omega }(g(x))$ Źle

$f(x)=\mathrm{\Theta }(g(x))$ Źle

$f(x)=O(g(x))$ Dobrze

$f(x)=o(g(x))$ Dobrze

Dla $f(x)=x^2$ oraz $g(x)=x^2+\sin x$ zachodzi:

$f(x)=\mathrm{\Omega }(g(x))$ Dobrze

$f(x)=\mathrm{\Theta }(g(x))$ Dobrze

$f(x)=O(g(x))$ Dobrze

żadne z pozostałych Źle

Dla $T(n)=9T(\frac{n}{3})+\frac{n^2}{\lg n}$:

możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2)$ Źle

możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2\lg n)$ Źle

możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(\frac{n^2}{\lg n})$ Źle

żadne z pozostałych Dobrze

Dla $T(n)=25T(\frac{n}{4})+\frac{n^2}{\lg n}$:

możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^{{\lg }_{4}25})$ Dobrze

możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2)$ Źle

możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(\frac{n^2}{\lg n})$ Źle

żadne z pozostałych Źle

Funkcja spełniająca zależność $T(n)=T(\frac{n}{2})+1$ jest:

$\mathrm{\Theta }(\lg n)$ Dobrze

$\mathrm{\Theta }(n)$ Dobrze

$O(n)$ Dobrze

żadne z pozostałych Źle