Notacja O.

[rNest]

Mam kłopot z metodyką rozwiązywania zadań związanych z notacją O.
Do rozwiązania mam 2 przykłady:

Dla poniższych ciągów znajdź najmniejszą liczbę k taką, że \(\displaystyle{ f(n)=O(n ^{k} )}\):

a).\(\displaystyle{ f(n)=13n ^{2}+4n-73}\)

b).\(\displaystyle{ f(n)=(n ^{2}+1 )(2n ^{4}+3n-8 )}\)

Proszę o pomoc bardziej doświadczonych użytkowników.

[ksisquare]

\(\displaystyle{ n^k}\) od pewnego n, rośnie wolniej, niż \(\displaystyle{ }n^{k+\mbox{coś tam}}}\)
a) 2
b) 8

[Vardamir]

A trochę formalniej, zapis \(\displaystyle{ f(n)=O(n^k)}\) oznacza, że możemy funkcję \(\displaystyle{ f(n)}\) ograniczyć z góry dla pewnego \(\displaystyle{ C}\) w taki sposób:

\(\displaystyle{ f(n) \le C\cdot n^k}\)

dla dużych \(\displaystyle{ n}\). Odpowiedzi masz w poście powyżej.

[rNest]

Czyli bardziej szczegółowo do a) :

\(\displaystyle{ f(n)=13n ^{2}+4n-73}\)
\(\displaystyle{ 13n ^{2}+4n-73=0(n ^{k} )}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le C \cdot n ^{k}}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le 13n ^{2}+n ^{2} \le 14n ^{2}}\)
\(\displaystyle{ n ^{k}=n ^{2}, K=2.}\)

Czy powyższe jest ok ?
A jak będzie w punkcie b). ? Najpierw trzeba wymnożyć oba nawiasy?

[Vardamir]

Czy powyższe jest ok ?
A jak będzie w punkcie b). ? Najpierw trzeba wymnożyć oba nawiasy?

Tak i tak.

[rNest]

I jeszcze proszę o podpowiedź w poniższym:

Dla każdego z poniższych ciągów podaj ciąg \(\displaystyle{ a(n)}\) taki, że: \(\displaystyle{ f(n)=O(a(n))}\).
Czy tutaj wystarczy po prostu znaleźć odpowiednie ciągi ograniczające z góry i zamienić te pierwotne?

\(\displaystyle{ f(n)=n ^{3} \cdot log _{2}n}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n =O(n ^{3} ) \cdot O(log _{2}n )}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n \le n ^{4} \cdot \sqrt[3]{n}}\)
\(\displaystyle{ a(n)=n ^{4} \cdot \sqrt[3]{n}}\)