Notacja "O"

[technofetishist]

Treść zadania:

Znajdź najmniejsze \(\displaystyle{ k\in\mathbb{N}}\) dla którego \(\displaystyle{ f(n)=O(n^{k})}\):
\(\displaystyle{ f(n)=\sqrt{ n^{4}+n^{2} }}\)
Odpowiedź uzasadnij.

Moje rozwiązanie:

\(\displaystyle{ f(n)=\sqrt{ n^{4}+n^{2} }}\)
ponieważ \(\displaystyle{ n^{2} < n^{4}}\) dla \(\displaystyle{ n\in\mathbb{N}}\)

mamy \(\displaystyle{ \sqrt{n^{4}+n^{2}} < \sqrt{n^{4}+n^{4}}}\)

czyli \(\displaystyle{ g(n)=\sqrt{n^{4}+n^{4}}=\sqrt{2 \cdot n^{4}}= \sqrt{2} \cdot \sqrt{n^{4}}=\sqrt{2} \cdot n^{2}}\)

zatem \(\displaystyle{ g(n)=O(n^{2})}\), bo \(\displaystyle{ \exists_{C>0}g(n) qslant Cn^{2}}\), gdzie \(\displaystyle{ C= \sqrt{2}}\)

ponieważ \(\displaystyle{ \forall_{n\in\mathbb{N}}( f(n)}\)

[kadiii]

potrzebne jeszcze funkcja ograniczająca z dołu czyli np. \(\displaystyle{ \sqrt{n^{4}}< \sqrt{n^{4}+n^{2}}}\)i dalej tak samo jak zrobiłeś wcześniej. Zauważ, że jeśli byłoby tylko te twoje górne przybliżenie to mógłbyś wykazać dowolną asymptotę czyli straszna nieprawdę. Jeżeli chcesz korzystać z takiej metody musisz miec zawsze z dołu i z góry funkcje tego samego typu aby móc wyciagnąć sensowny wniosek.

[technofetishist]

potrzebne jeszcze funkcja ograniczająca z dołu czyli np. \(\displaystyle{ \sqrt{n^{4}}< \sqrt{n^{4}+n^{2}}}\)i dalej tak samo jak zrobiłeś wcześniej. Zauważ, że jeśli byłoby tylko te twoje górne przybliżenie to mógłbyś wykazać dowolną asymptotę czyli straszna nieprawdę. Jeżeli chcesz korzystać z takiej metody musisz miec zawsze z dołu i z góry funkcje tego samego typu aby móc wyciagnąć sensowny wniosek.

Masz rację, natomiast na zajęciach - bo to zadanie ze studiów - sprawdzaliśmy tylko górne ograniczenia, zatem wystarczy mi (do zaliczenia) to.

Skoro jest poprawnie, to cieszę się.

[kadiii]

Jeżeli jesteś pewien, że tak cie uczyli to ok. Dla mnie to jednak trochę dziwne, w rozwiązaniu korzysta się z tego, że z góry oszacowujesz wynik i tak dobierasz funkcję, zapis powinien być według mnie więc pełny. Równie dobrze mógłbyś napisać odrazu wynik, bo przecież go widać - skoro jednak chce sie coś udowodnić to trzeba to robić dobrze. Z tego rozumowania można jedynie wywnioskowość, że jest to \(\displaystyle{ O(n^2) O(n) O(1)}\) i nic wiecej.