[Teoria złożoności] Notacja asymptotyczna

nowyyyy4 · Post autor: **nowyyyy4** » 29 lis 2014, o 18:14

Mam sprawdzić czy \(\displaystyle{ 5n^3+2n^2+100 = \Omega (n^4)}\)
Wg mnie nie, bo jest nie można tego wyrażenia oszacować z dołu przez \(\displaystyle{ cn^4}\) dla \(\displaystyle{ c>0}\), ale jak to uzasadnić?

Adifek · Post autor: **Adifek** » 29 lis 2014, o 18:31

Zbadać granicę

\(\displaystyle{ \lim_{n\to\infty} \frac{cn^4}{5n^3+2n^2+100}}\)

nowyyyy4 · Post autor: **nowyyyy4** » 29 lis 2014, o 19:15

A np. z czego skorzystać aby stwierdzić, że \(\displaystyle{ \left( \lg n \right) ^2 \neq O \left( \log n \right)}\)?

Adifek · Post autor: **Adifek** » 29 lis 2014, o 21:19

Z tego samego.

nowyyyy4 · Post autor: **nowyyyy4** » 30 lis 2014, o 10:35

\(\displaystyle{ \lim_{n \to \infty} \frac{(\lg n^2)}{c \log n}= +\infty}\)?

Medea 2 · Post autor: **Medea 2** » 30 lis 2014, o 11:29

Jeżeli tak to naiszesz, to nie jest prawdą (bo \(\displaystyle{ \log n^2 = 2 \log n}\)). Przestaw nawiasy.