forum.zadania.info

Uporządkuj podaną poniżej listę funkcji rosnąco względem szybkości ich wzrostu, tzn. jeśli
funkcja g(n) następuje bezpośrednio po funkcji f(n) w tym porządku, to f(n) jest rzędu
O(g(n)). Swoją odpowiedź uzasadnij.

\(f_1(n) = 2^{lg n}\), \(f_2(n) = 10n + lgn + 2020\), \(f_3(n) = 200n^2 + 5\), \(f_4(n) = lg(n!)\), \(f_5(n) = 2^{n+1}\), \(f_6(n) = 20n^3\)

Policz pochodne względem n.

Albo skorzystać z twierdzenia:
Jeżeli \( \displaystyle \Lim_{n\to \infty } \frac{f(n)}{g(n)}=k \wedge k\in\langle0,\infty) \), to \(f(n)=O(g(n))\)

A to \( lgn\) to jaki logarytm?

Jeśli \(lg\) to logarytm naturalny, to może się przydać fakt, że \(\ln n!\ge \frac{1}{2}n\ln n \)