Uzyć symbolu O do oszacowania wartości wyrażenia

[freak91]

Mam oszacować następujące wyrażenie:
\(\displaystyle{ f(n)=(1+\frac{1}{n})^n}\)

Definicja notacji O:
Mówimy, że \(\displaystyle{ f(n)=O(g(n))}\), jeżeli możemy wskazać dwie dodanie liczby \(\displaystyle{ n_0}\) oraz \(\displaystyle{ c}\) takie, że:
\(\displaystyle{ 0 \le f(n) \le c g(n)}\)
dla dowolnego \(\displaystyle{ n \ge n_0}\).

Zapisałem więc:
\(\displaystyle{ (1) 0 \le (1+\frac{1}{n})^n \le c (1+\frac{1}{n})^n}\)
Mogę podzielić przez wartość w nawiasie, ponieważ jest zawsze większa od 0.
\(\displaystyle{ 0 \le 1 \le c}\)

Wybrałem \(\displaystyle{ n_0 = 1}\) oraz \(\displaystyle{ c = 11}\).

Wstawiam do \(\displaystyle{ (1)}\), w zasadzie mogę zapisać:
\(\displaystyle{ 1 \le 11}\)
Jest to prawda. Pytanie jak się to fachowi robi. I czy o to chodzi?

[norwimaj]

To prawda, że \(\displaystyle{ \left(1+\frac1n\right)^n=O\left(\left(1+\frac1n\right)^n\right)}\), ale lepszym szacowaniem jest \(\displaystyle{ \left(1+\frac1n\right)^n=O(1)}\), co znaczy tyle że \(\displaystyle{ \left(1+\frac1n\right)^n}\) jest ciągiem ograniczonym.

[freak91]

Okay, czyli zawsze jak mam ciąg ograniczony to O(1). Ciąg ten w nieskończoności dąży do e.

Już zapomniałem wiele z tej najbardziej podstawowej analizy, ale czy ciąg jest ograniczony zawsze wtedy, gdy posiada granicę właściwą, przy \(\displaystyle{ n \to \infty}\), czy potrzeba sprawdzać coś jeszcze?

[norwimaj]

Gdy ma granicę właściwą to jest ograniczony.

[freak91]

Okay. A wezmę teraz taką funkcję:
\(\displaystyle{ f(n)=n+\lg(n)}\)

Korzystając z tej samej definicji, napiszę że:
\(\displaystyle{ 0 \le n + lgn \le cn}\)
Prawda dla \(\displaystyle{ c = 1\\ n_0 = 1}\).

Wniosek:
\(\displaystyle{ O(n+lgn)=O(n)}\)
Czyli jest to złożoność liniowa.

Zgadza się?

[norwimaj]

Nie możesz wziąć \(\displaystyle{ c=1}\), bo nieprawda że \(\displaystyle{ n+\lg n\le n}\), ale masz rację, że \(\displaystyle{ n+\lg n=O(n)}\).

[freak91]

Dzięki, niedopatrzenie.

Teraz walczę z taką funkcją:
\(\displaystyle{ f(n)=\frac{lgn}{\sqrt[n]{n}}}\)
Zapisałem ją jako:
\(\displaystyle{ f(n)=-lgn}\)

Jest to funkcja, która maleje. Raczej nie dam rady oszacować jej za pomocą notacji O. Mogę natomiast spróbować oszacować ją od dołu, stosując notację \(\displaystyle{ \Omega}\).

Jej definicja jest następująca:
Mówimy, że \(\displaystyle{ \Omega(g(n)) = f(n)}\) jeżeli istnieją dodatnie stałe \(\displaystyle{ c}\) i \(\displaystyle{ n_0}\) takie, że \(\displaystyle{ 0 \le c g(n) \le f(n)}\) dla wszystkich \(\displaystyle{ n \ge n_0}\).

Postępuje więc analogicznie jak w notacji O.

\(\displaystyle{ 0 \le -c lg n \le -lg n}\)
dla \(\displaystyle{ c = 1\\ n_0=2}\)
\(\displaystyle{ f(n) = \Omega(lgn)}\)

[Mistrz]

\(\displaystyle{ \frac{\ln n}{\sqrt[n]{n}}}\) nie jest tą samą funkcją co \(\displaystyle{ -\ln n}\). Natomiast prawdziwe są nierówności \(\displaystyle{ 1 \le \sqrt[n]{n} \le 2}\).

[freak91]

EDIT: już widzę błąd.