Zadanie 1

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

Zadanie 2

Pokaż, że jeśli b>1, T,S - niemalejące, T(b^k) = Θ(S(b^k)) 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) = n^a; (b) S(n) = aⁿ.

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 2ⁿ czy liczba końcowych zer w zapisie dziesiętnym liczby n!.

Zadanie 4

Niech f(n) będzie rozwiązaniem równania funkcyjnego x log¹⁰⁰¹x = 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\).