Matematyka dyskretna 1/Test 9: Asymptotyka

From Studia Informatyczne

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

\displaystyle \Theta(n^2\lg{n})

\displaystyle O(n^2\lg{n})

\displaystyle \Theta{n^2\sqrt{n}}

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


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

\displaystyle O(n^{\frac{9}{10}})

\displaystyle O(n)

\displaystyle O(n^9)

\displaystyle \Omega(\lg^{10}n)


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

\displaystyle f(x)=\omega(g(x))

\displaystyle f(x)=\Omega(g(x))

\displaystyle f(x)=\Theta(g(x))

\displaystyle f(x)=O(g(x))

\displaystyle f(x)=o(g(x))


Dowolny wielomian \displaystyle k-tego stopnia jest:}

\displaystyle \Omega(n^k)

\displaystyle \Theta(n^k)

\displaystyle O(n^k)

\displaystyle o(n^{k+\varepsilon}) dla dowolnego \displaystyle \varepsilon>0


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

\displaystyle f(x)=\omega(g(x))

\displaystyle f(x)=\Omega(g(x))

\displaystyle f(x)=\Theta(g(x))

\displaystyle f(x)=O(g(x))

\displaystyle f(x)=o(g(x))


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

\displaystyle f(x)=\Omega(g(x))

\displaystyle f(x)=\Theta(g(x))

\displaystyle f(x)=O(g(x))

żadne z pozostałych


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

możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i \displaystyle T(n)=\Theta(n^2)

możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i \displaystyle T(n)=\Theta(n^2\lg n)

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

żadne z pozostałych


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

możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i \displaystyle T(n)=\Theta(n^{\lg_4{25}})

możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i \displaystyle T(n)=\Theta(n^2)

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

żadne z pozostałych


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

\displaystyle \Theta(\lg n)

\displaystyle \Theta(n)

\displaystyle O(n)

żadne z pozostałych