1. Welche Rechenregeln für Logarithmen gibt es?
2. Vereinfache die folgenden Terme:
   • $\log_2(8)$
   • $\log_3(1)$
   • $\log_2(n^4)$
   • $\log_{10}\left(\frac{1}{n^2}\right)$
   • $2^{\log_4(n)}$
   • $\log_n(n)$
   • $\log_a(b) \cdot \log_b(n)$
   • $\log_2(4n^3)$
   • $\log_2(\sqrt{n})$
   • $\log_2\left( \sum_{i=0}^n i \right)$
   • $\log_3\left(\prod_{i=1}^n 3^i \right)$
   • $\sum_{i=1}^n n \cdot i$
   • $\sum_{k=0}^n 2^{-k}$
   • $\sum_{k=1}^{\frac{n}{2}} 4^{-k}$
   • $\sum_{i=1}^n \frac{2}{i} <\underline{\qquad}$
3. Wahr oder falsch? Begründe deine Antwort.
   • $1 = \Theta(3)$
   • $2 = \Omega(1)$
   • $3 = \omega(2)$
   • $n = \omega(1)$
   • $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f) \iff f = \Theta(g)$
   • $\sum_{k=0}^n 2^{-k} = \mathcal{O}(1)$
   • $\log_2(n) = \Theta(\log_8(n))$
   • $2^{\log_2(2n)} = \mathcal{O}(n^2)$
   • $f_1 = \Omega(g_1)$ und $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$
   • $f = o(g) \iff f = \mathcal{O}(g)$
   • $f(n) = g(\frac{n}{2}) \implies f = \Omega(g)$
   • $f = o(g) \implies 2^f = o(2^g)$

Welchen Wert hat k in Abhängigkeit von n nach der Ausführung des Programms?

1. k = 1
   for i=1,2,...,n
       k = k + 1

2. k = 1
   for i=1,2,...,n
       k = k + 1
   for j=1,2,...,100
       k = k + 2

3. k = 1
   for i=1,2,...,n*n
       k = k + 2

4. k = 1
   for i=n,n/2,n/4...,1
       k = k + 1

5. k = 1
   for i=1,2,...,n
       k = k + i

6. k = 1
   while i < n
       i = i + i
       k = k + 1

7. i = 0
   k = 0
   while i < n
       i = i + k
       k = k + 1

Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten:

1. $\Theta(1)$
2. $\Theta(n)$
3. $\Theta(n^3)$
4. $\Theta(2^n)$
5. $\Theta(\sqrt{n})$
6. $\Theta(\log{n})$
7. $\Theta(\log{n^3})$
8. $\Theta(n!)$

Aufstellen:

1. def f(n):
       if n == 1
           return 1
       else
           return n + f(n-1)

2. def g(n):
       if n > 1:
           return g(n/2)

Lösen:

1. $T(1) = 0$ und $T(n) = 2 T(\frac{n}{2}) + \frac{n}{2}$ für $n > 1$
2. $T(2) = 1$ und $T(n) = T(\frac{n}{2}) + n - 1$