# Algorithmen und Datenstrukturen: Blatt 2

## Aufgabe 1


Laufzeit: $T(n)= \Theta(n^2)+3\Theta(n^2) = \Theta(n^2)$
$c_1=1$
$c_2=5$
$n_0=1$
$\Rightarrow 1*n^2 \leq \Theta(n^2)+3\Theta(n^2) \leq 5*n^2$


Laufzeit: $T(n)=\Theta(1)+\Theta(n)+\Theta(n) = \Theta(n)$
$c_1=1$
$c_2=3$
$n_0=1$
$\Rightarrow 1*n^2 \leq \Theta(1)+\Theta(n)+\Theta(n) \leq 3*n$


Laufzeit:
$T(n)=\Theta(1)+\Theta(n)*(\Theta(n)+\Theta(1))+\Theta(1) = \Theta(n^2)$
$c_1=1$
$c_2= 2$
$n_0=1$
$\Rightarrow 1*n^2 \leq \Theta(1)+\Theta(n^2)+\Theta(1)\leq 2*n^2$

## Aufgabe 2

### a)

$f_6\prec f_1 \prec f_3 \prec f_2 \prec$ {$f_5,f_7$}$\prec f_4$,
da $f_6\in O(log(n)), f_1 \in O(n (log (n))),f_3 \in O(n^{\frac{3}{2}}),
f_2 \in O(n^2), f_5 \land f_7 \in O(n^3),f_4 \in O(n^n)$

### b)

Zu zeigen:

- $\frac{1}{2000} n^3 \in \Omega(n^2)$:
$\lim_{n \to \infty} \frac{\frac{1}{2000}n^3}{n^2}=
\lim_{n \to \infty}\frac{1}{2000} n=\infty$
$\Rightarrow$ $\frac{1}{2000} n^3$ ist somit in
$\Omega(n^2)$ und in $\omega(n^2)$,
da gilt $c=\infty$ und $0\leq c< \infty$

- $5000n^2+ 125n\in o(n^3)$
$\lim_{n \to \infty} \frac {5000n^2+125n}{n^3}=\lim_{n \to \infty} \frac {5000n +125n}{n^2}=0$
$\Rightarrow 5000n+125n$ ist somit in $o(n^3)$ und in $O(n^3)$,
da gilt $c=0$ und somit $0\leq c<\infty$

- $3(\log n)^2+ 7\in \omega (\log n)$
$\lim_{n \to \infty} \frac {3(\log n)^2+ 7}{\log n}=
\lim_{n \to \infty} 3 \log n = \infty$
$\Rightarrow$ $3(\log n)^2 +7$ ist somit in
$\Omega(n^2)$ und in $\omega(n^2)$,
da gilt $c=\infty$ und $0\leq c< \infty$

## Aufgabe 3

Zu zeigen: Für beliebige Funktionen $f$, $g$, $h$, gilt:
$f \in O(g) \land g \in O(h) \Rightarrow f \in O(h$).

$\exists c_1,n_1: \forall n \geq n_1: f(n) \leq c_1 \cdot g(n) \land$
$\exists c_2,n_2: \forall n \geq n_2: g(n)\leq c_2 \cdot h(n)$
$\Rightarrow \exists c_3,n_3: \forall n \geq n_3: f(n) \leq c_3 \cdot h(n)$
für $c_3 = c1 \cdot c2$ und $n_3 = max(n_1,n_2)$

## Verbesserung

### zu Aufgabe 1

#### Algorithmus 1

| Zeile | Ausführungen |
| ----- | --------------- |
| 1 | 1 |
| 4 | $n \cdot (n-1)$ |
| 5 | $n \cdot (n-1)$ |
| 6 | $n \cdot (n-1)$ |
$\Rightarrow$ foo wird $1+3n(n-2)=3n^2-6n+1$ mal ausgeführt.
Behauptung: $3n^2 - 6n + 1 \in \Theta(n^2)$
zz: $c_1n^2 \leq 3n^2 - 6n +1 \leq c_2n^2$ für $c_1=1, c_2=3, n \geq n_0=3$
Nebengedanken: $c_1n^2 \leq 3n^2 -6n +1$
$c_1 \leq 3- \frac{6}{n} + frac{1}{n^2}$
$n=3: c_1 \leq 3.2+\frac{1}{9} = 1+ \frac{1}{9}$

#### Algorithmus 2

| Zeile | Ausführungen |
| ----- | ------------- |
| 1 | 1 |
| 3 | $n$ |
| 6 | $\frac{n}{2}$ |
| 7 | $\frac{n}{2}$ |
$\Rightarrow$ foo wird $1+ n+2(\frac{n}{2}) = 2n+1$ ausgeführt.
Behauptung: $2n+1 \in \Theta(n)$
$c_1\leq 2n+1 \leq c_2n$ für $c_1= 2, c_2=3, n\geq n_0 = 1$

#### Algorithmus 3

| Zeile | Ausführungen |
| ----- | ------------------------------------ |
| 1 | 1 |
| 4 | $\sum_{i=1}^{n}i = \frac{n(n+1)}{2}$ |
| 6 | $n$ |
| 8 | $1$ |
$\Rightarrow$ foo wird $1+\frac{n(n+1)}{2}+n+1 =
\frac{n^2}{2} + \frac{3n}{2} +2$ mal ausgeführt.
Behauptung: $\frac{n^2}{2} + \frac{3n}{2} +2 \in \Theta(n^2)$
denn $c_1n^2 \leq \frac{n^2}{2} + \frac{3n}{2} +2 \leq c_2n^2$
für $c_1=\frac{1}{2}, c_2=4, n\geq n_0 = 1$

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