Asymptotyczne tempo wzrostu uporządkowanie

[Cybran]

Witam!
BArdzo prosiłbym o pomoc w rozwiązaniu takich 2 zadań. Prowadzący zrobił na ten temat uwagę na kwadrans przed końcem wykładu, nic nie tłumacząc, a teraz dał zadania.

Chodzi o porównywanie co jest O duże coś innego.

Tak jak ja to rozumiem, to po prostu muszę popatrzeć, która najbliższa funkcja ogranicza którą. Ale o ile rozumiem, że na przykład złożonośc wzrostu potęgowego jest mniejsza (szybciej rośnie) niż wykładniczego, o tyle zupelnie glupieję w przykładach, gdy mam np. "WOLNIEJSZĄ" FUNKCJĘ W "SZYBSZEJ" (np. logarytm pod pierwiastkiem). Mógłby ktoś mi to wytłumaczyć nawet na 1,2 przykładach?

zad. 1 uporządkuj wg. asymptotycznego zachowania:
\(\displaystyle{ n ^{2}, nlog _{2}n , n \sqrt{n} , \sqrt{n}log _{2}n, \frac{log _{2}n}{n}, log _{2}(n ^{5} ), n ^{n} , log _{2}(log _{2}n )}\)


zad 2. Dla każdego z podanych ciągów znajdź taką liczbę k (możliwie jak najmniejszą), że \(\displaystyle{ f(n)=O(n ^{k} )}\).

\(\displaystyle{ f(n)=13n ^{2} +4n-73}\)
\(\displaystyle{ f(n)=(n ^{2} +1)(2n ^{4} +3n-8)}\)
\(\displaystyle{ f(n)= \sqrt{n ^{2}-1 }}\)


Z góry wielkie wielkie dzięki!!!

[adek05]

1. Jeżeli nie masz wyczucia co jest większe to... z definicji, np. przez liczenie granic ilorazów.
2. Strzel i udowodnij.