# AlgoDat Tutorium 3

## Aufgabe 1

Rekursionsgleichung: $T(n)=2 \cdot T(n/2) + n$

### 1a)

Behauptung: $\exists c > 0$, sodass gilt: $T(n) \leq c \cdot n \cdot log(n)$
T(1)?
Induktionsannahme: $T(k) \leq c \cdot k \cdot log(k), k<n$
Induktionsschluss:
$T(n)=2 \cdot T(n/2) + n$
$\leq 2c \cdot n/2 \cdot log(n/2) +n$
$=cn \cdot (log_2 n - log_2 2)+n = cn \cdot log_2 n - cn + n = cn \cdot log_2 n + n(1-c)$
$\leq cn\cdot log_2 n$ für $c \geq 1$.

### 1b)


| Ebene | Knotenanzahl | Beitrag |
| -------- | ------------ | ---------------------- |
| $0$ | $2^0 = 1$ | $n$ |
| $1$ | $2^1 = 2$ | $\frac{n}{2}$ |
| $2$ | $2^2 = 4$ | $\frac{n}{4}$ |
| ... | ... | ... |
| $i$ | $2^i$ | $\frac{n}{2^i}$ |
| ... | ... | ... |
| $log_2n$ | $2^{log_2n}$ | $\frac{n}{2^{log_2n}}$ |

$T(n) = 1+ \sum_{i=0}^{(log_2n)-1}\frac{n}{2^i}
\leq 1+n \cdot \sum_{i=0}^{\infty} (\frac{1}{2})^i =
1+2n$ (, da $x^i=\frac{1}{1-x}$)
$\Rightarrow T \in O(n)$

### 1c)

$a = 2, b = 2, f(n) = n$
$\Rightarrow$ Fall 2: $f \in \Theta n^{log_2 2} = n$
$\Rightarrow: T(n) \in \Theta(n \cdot log n)$

## Aufgabe 2

### 2a)


### 2b)

$T(n) = 2T(n-1) + a$
$a :=$ Laufzeit von MoveDiskOnTopFromTo$(S_1, S_3)$

### 2c)

Induktionsanfang: $n = 1$:
move(0, s1, s3, s2)
moveTop(s1, s3)
--> wandert auf s3
move(0, s2, s1, s3)
offensichtlich richtig

Induktionsannahme: Gilt für k < n Scheiben.
Induktionsschluss: n = k+1

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`