Szacowanie ciągu

[kamilpz]

Cześć, nie mogę sobie poradzić z uzasadnieniem (bo wiadomo, że równość jest prawdziwa, to znaczy ciąg po lewej nie rośnie szybciej niż pierwiastek z n):
Sprawdź, czy podana równość jest prawdziwa:
\(\displaystyle{ (log_{2}n)^{73}=O( \sqrt{n})}\)

Robię tak:
\(\displaystyle{ (log_{2}n)^{73} \le C \cdot \sqrt{n}}\)
\(\displaystyle{ (log_{2}n)^{146} \le C_{1} \cdot n}\)
wprowadzam: \(\displaystyle{ y = log_{2}n}\)
oraz: \(\displaystyle{ n = 2^{y}}\)
teraz:
\(\displaystyle{ y^{146} \le C_{1} \cdot 2^{y}}\)

Ostatnia linijka się zgadza dla dostatecznie dużych y, ale można to wyznaczyć?

[JakimPL]

Wynika to stąd, iż dla dowolnego \(\displaystyle{ k\in\mathbb{R}}\) i \(\displaystyle{ a>1}\):

\(\displaystyle{ \frac{y^k}{a^y}\to 0}\)

Wystarczy wyznaczyć odpowiednią granicę. W Twoim przykładzie:

\(\displaystyle{ \frac{\log^{73}_{2}n}{\sqrt{n}} \to 0}\)

\(\displaystyle{ \log^{73}_{2}n - \sqrt{n} \to -\infty}\)

[kamilpz]

Wiem już, jak to ma być. Patrząc na ostatnią nierówność:
\(\displaystyle{ y^{146} \le 2^{y}}\)
można wziąć logarytm z tego:
\(\displaystyle{ log _{2} (y^{146}) \le log _{2} (2^{y})}\)
\(\displaystyle{ 146 \cdot log _{2} (y) \le y}\)
Na pewno musi też zajść nierówność:
\(\displaystyle{ 146 \cdot \sqrt{y} \le y}\)
Czyli:
\(\displaystyle{ y \ge 146^{2}}\)
Czyli:
\(\displaystyle{ n \ge 2^{146^{2}}}\)
Dobrze myślę? Czyli odpowiedź będzie, że dla dostatecznie dużych n \(\displaystyle{ (log_{2}n)^{73}}\) rośnie wolniej niż \(\displaystyle{ \sqrt{n}}\).

[JakimPL]

Wniosek masz dobry, ale nie wiem, na ile "czujesz", że tak musi być, jak napisałeś. Wypadałoby to rozumowanie uporządkować i sformalizować (wykorzystując definicję notacji \(\displaystyle{ O}\)). Nie do końca rozumiem przejścia z logarytmu do pierwiastka.

Musisz sobie uświadomić, jaki asymptotycznie charakter ma logarytm, funkcja wielomianowa, a jaki charakter ma funkcja wykładnicza. Wtedy ten wyliczony wniosek będzie oczywisty.

[kamilpz]

Dzięki za odpowiedź. Przejście z logarytmu na pierwiastek podpatrzyłem w innym przykładzie. Pozwala dalej poprowadzić rozumowanie, chociaż oczywiście moje oszacowanie jest przez to mniej dokładne.
Temat jest fajny i faktycznie wymaga poznania charakteru tych funkcji. Pozdrawiam:)

[JakimPL]

W wypadku notacji "duże O", łatwo korzysta się z granic, dokładniej:

\(\displaystyle{ \lim_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| < \infty \Rightarrow f(x) \in O(g(x))}\)

To jest warunek wystarczający i "omija" liczenie na piechotę.