Notacja asymptotyczna - dowód

[rekja]

Witam Szanownych Forumowiczów

Od dłuższego czasu borykam się z pewnym zadaniem (tematem), przewertowałem kilka książek, kilkadziesiąt stron www i nie mogę poradzić sobie z:

Pokaż, że \(\displaystyle{ \frac{1}{2}n^3 - 2n = \Omega(n^3)}\).

Za wszelkie uwagi i sugestie z góry dziękuję. Pozdrawiam

[Premislav]

... 9%E2%80%9D

Zauważmy, że gdy \(\displaystyle{ n\ge 4}\), to
\(\displaystyle{ \frac{1}{2}n^3 - 2n\ge \frac 3 8n^3 \Leftrightarrow \\ \Leftrightarrow \frac 1 8 n^3-2n\ge 0 \Leftrightarrow \\ \Leftrightarrow \frac 1 8 n\left( n^2-16\right) \ge 0}\)
co oczywiście jest prawdą.

[rekja]

OK, dziękuję za podpowiedz, czyli jeżeli dobrze zrozumiałem to:

Czy \(\displaystyle{ 2^{n+1} = \mathcal{O}(2^n)}\) ?

\(\displaystyle{ 2^{n+1} \le 2^n \Leftrightarrow \\
2 \cdot 2^n \le 2^n \Leftrightarrow \\
1 \le 0}\)
co nie jest prawdą, czyli powyższy zapis również nie jest prawdziwy?


Albo:
Czy \(\displaystyle{ 2^{2n} = \mathcal{O}(2^n)}\) ?

\(\displaystyle{ 2^{2n} \le 2^n \Leftrightarrow \\
2^n \cdot 2^n \le 2^n \Leftrightarrow \\
2^n -1 \le 0}\)
co nie jest prawdą gdy \(\displaystyle{ n \ge 1}\), czyli powyższy zapis również nie jest prawdziwy?


Zastanawiam się jeszcze nad tym:
Udowodnij, że \(\displaystyle{ f(n) = \Theta(g(n))$ wtw $f(n) = \mathcal{O}(g(n))$ oraz $f(n) = \Omega(g(n))}\) .

[Premislav]

No nie bardzo, przecież zachodzi \(\displaystyle{ 2^{n+1}\le 2\cdot 2^n}\) (a nawet jest równość), czyli \(\displaystyle{ 2^{n+1} = \mathcal{O}(2^n)}\).

Co do tamtego dowodu, wystarczy skorzystać bezpośrednio z definicji tych symboli (można ich nie znać albo nie pamiętać, ale to po to podałem link, żeby ew. przypomnieć).

[rekja]

zapomniałem o \(\displaystyle{ c}\), zgodnie z definicją:

\(\displaystyle{ \mathcal{O}(g(n)) = \{f(n):}\) istnieje stała \(\displaystyle{ c}\) taka, że dla pewnego \(\displaystyle{ n_0}\), \(\displaystyle{ \forall n \geq n_0, f(n) \leq c\cdot g(n) \}}\)

czyli w tym przypadku:
\(\displaystyle{ 2^{n+1} \le 2 \cdot 2^n}\)
odpowiednio będą
\(\displaystyle{ f(n)}\) to \(\displaystyle{ 2^{n+1}}\)
\(\displaystyle{ c}\) to \(\displaystyle{ 2}\)
a \(\displaystyle{ g(n)}\) to \(\displaystyle{ 2^n}\)

a drugi przykład również jest prawdziwy?

\(\displaystyle{ 2^{2n} \le c \cdot 2^n\\
2^n \le c}\)
z tego wynika, że \(\displaystyle{ c}\) jest zależne od \(\displaystyle{ n}\)

[Premislav]

z tego wynika, że c jest zależne od \(\displaystyle{ n}\)

Tak być nie może. Rzecz jasna \(\displaystyle{ 2^{2n}\neq \mathcal{O}\left(2^n\right)}\). Powód zresztą jest taki, że
\(\displaystyle{ \lim_{n \to \infty } \frac{2^{2n}}{2^n} =+\infty}\).