Notacje asymptotyczne wcale nie sympatyczne...

[Raqil]

Witam serdecznie wszystkich forumowiczów

Mam głęboką prośbę... To jest mój pierwszy post.. Nie wiem czy w dobrym miejscu go umiejscawiam.. Mam nadzieję, że tak.. Jestem nowym użytkownikiem na tym forum.. Byłem zmuszony się zarejestrować ponieważ już nie mam gdzie, ani do kogo się zgłosić o pomoc

Czy znalazłaby się osoba, która pomogłaby mi rozwikłać poniższe 12 zagadnień związane z notacjami? Mnie osobiście już nic nie przychodzi do głowy, a rozwiązanie jest dla mnie bardzo istotne ponieważ za dwa dni mam zaliczenie i chciałbym choć odrobinę zrozumieć z tego, jak.. co,.. z czego..

Oto "treść" zadania:

Zbadać, czy..
1) \(\displaystyle{ log_{3}(n^{84}) = O(lg (n))}\)

2) \(\displaystyle{ w(n)=O(n^{k})}\), gdzie \(\displaystyle{ w(n)=a_{k} \cdot n^{k}+a_{k-1} \cdot n^{k-1} + \dots + a_{1} \cdot n + a_{0}, a_{i} \in R, i=0,1,2,...,k \text{ } a_{k}>0 \text{ } k \in N}\)

3) \(\displaystyle{ n^{0.9}lg(n) = o(n)}\)

4) \(\displaystyle{ n^{\frac{3}{4}}+lg(n^{4})+10000 = o(n)}\)

5) \(\displaystyle{ \sqrt[10]{n}+20lg(n)^{456} = \Theta(\sqrt[10]{n})}\)

6) \(\displaystyle{ 2^{n}lg(n)+n! = \Theta(n!)}\)

7) \(\displaystyle{ \frac{n}{lg(n)} = \Omega(lg(n))}\)

8) \(\displaystyle{ \frac{n^{2}}{ \sqrt{n+lg(n)} } = \Omega(lg(n))}\)

9) \(\displaystyle{ lg (n^{n})=O(lg (n))}\)

10) \(\displaystyle{ (n+1)! = \Omega(n!)}\)

11) \(\displaystyle{ 16^{n} = \Theta(2^{n})}\)

12) \(\displaystyle{ n^{2} = o(\frac{n^{\frac{3}{2}}}{lg(n)^{6}})}\)

Z góry dziękuje za wszelką pomoc jak również za bezcenne wskazówki, które mogłyby pomóc w rozwiązywaniu tego typu zadań. Hmm.. a może macie jakieś swoje techniki, którymi moglibyście się podzielić, aby łatwiej i szybciej uporać się z takimi notacjami?

Byłbym ogromnie wdzięczny za każdą radę.

Pozdrawiam serdecznie

[Dumel]

no to np. 9.
gdyby to była prawda to istniałaby stała A spełniająca:
\(\displaystyle{ \lg n^n=n \lg n \le A \lg n}\)
oczywiście nie może to być prawdą przy \(\displaystyle{ n \to \infty}\)