Aufgabe O-Notation:
1. Sortieren Sie die folgenden Laufzeiten aufsteigend. (Wenn \( f(n)=O(g(n)) \), aber nicht \( g(n)=O(f(n)) \), dann soll \( f(n) \) vor \( g(n) \) stehen.)
(a) \( n^{3} \)
(b) \( \log _{2} n \)
(c) \( 1,8^{n} \)
(d) \( n \)
(e) \( 3^{n} \) (f) \( \sqrt{n} \)
(g) \( n\left(\log _{2} n\right)^{2} \)
(h) \( n^{2} \)
2. Angenommen, ein Programm hat Laufzeit \( f(n) \), wobei \( f(n) \) eine der Funktionen aus Teil (a) ist. Nehmen Sie weiter an, dass in zehn Jahren die Computer 1000 mal schneller sind als heute. Probleme welcher Größe kann man dann in derselben Zeit lösen, die man heute für Probleme der Größe \( n=20 \) braucht?
