Ćwiczenia 9: asymptotyka - podstawowe pojęcia

Zadanie 1

Podaj przykład funkcji f takiej, że f(n) = ω((log n)a) oraz f(n) = o(nb) dla dowolnych a,b>0.

Zadanie 2

Pokaż, że jeśli b>1, T,S - niemalejące, T(bk) = Θ(S(bk)) i dodatkowo S spełnia warunek
S(bn) = Θ(S(n))
to T(n) = Θ(S(n)).
Sprawdź, czy ten warunek jest spełniony dla (a) S(n) = na; (b) S(n) = an.

Zadanie 3

Niech n oznacza łączną liczbę włosów na głowach wszystkich ludzi żyjących obecnie na Ziemi. Rozstrzygnij, co jest większe: długość zapisu dziesiętnego liczby 2n czy liczba końcowych zer w zapisie dziesiętnym liczby n!.

Zadanie 4

Niech f(n) będzie rozwiązaniem równania funkcyjnego x log1001x = n. Znajdź rząd wielkości funkcji f.

Zadanie 5

Znajdź rząd wielkości funkcji f(n) określonej zależnością \(f(n)^{f(n)^{f(n)}} = n\) dla \(n>0\).