# Algorithmen und Datenstrukturen: Blatt 3

## Aufgabe 1

### 1a)

zz: $O(\sqrt {n}) = O(n)$
Die Aussage ist wahr. Es gilt $O(\sqrt{n}) = O(n^{0,5})$.

Eine exponentielle Funktion wächst schneller, um so größer ihr Exponent ist.
Deshalb wächst die Funktion $n^1 = n$ schneller,
als die Funktion $n^{0,5}$ (da $1 < 0,5$).
Umgekehrt folgt daraus allerdings,
dass die Funktion $\sqrt{n}$ höchstens so schnell wächst, wie die Funktion $n$.
Das wiederum ist genau die Bedeutung der Aussage $O(\sqrt {n}) = O(n)$.

### 1b)

zz: $n+ o(n^2)= \omega (n)$

### 1c)

zz: $3n \log n + O(n) = \Theta (n \log n)$
$3n \log n \in \Theta (n \log n)$.
Es gilt $3n \log n \in O (n \log n)$,
sodass gilt $O(n \log n)+ O(n)= O(n log n)$,
da $(n \log n)$ die Funktion ist,
die stärker wächst und dadurch $O(n)$ absorbiert.
Somit ist $3n \log n + O(n) = \Theta (n \log n)$ $

## Aufgabe 2

Fall 1: $n \in {1,2}$
Aus der Defintion der Funktion geht hervor, dass $f(1)=1$ und $f(2)=2$.
Somit wächst hier die Funktion linear und
$T(n)$ für $n\in {1,2}$ gilt $T(n) \in O(n)$

Fall 2: $n >2$
Um zu zeigen, dass $T(n) \in O(n)$.
Dafür zeigen wir, dass $cn-d$ existiert mit $T(n)\leq cn-d$.
Beweis durch Induktion:
IA: $T(k) \leq ck-d$
$T(n)= T(\lfloor \frac {n}{2}\rfloor)+T(\lfloor \frac {n}{3}\rfloor)+n$
$\leq (c\lfloor \frac {n}{2}\rfloor -d)+(c\lfloor \frac {n}{3}\rfloor -d )+n
=c\lfloor \frac {n}{2}\rfloor -d+c\lfloor \frac {n}{3}\rfloor -d+n$
$=c\lfloor \frac {n}{2}\rfloor+c\lfloor \frac {n}{3}\rfloor-d+n-d=
c\lfloor \frac{5n}{6} \rfloor-d+(n-d)$
$\leq c\lfloor \frac{5n}{6} \rfloor -d$ für $d \geq 1$
Somit ist $T(n) \in O(n)$ auch für n>2.

## Aufgabe 3

### 3a)

$T(n) = 2 T(\frac{n}{2})+n$
Es ist Fall 2 erfüllt: $a=2, b=2, f(n) = n$.
Denn es gilt:
$f(n) = n \in \Theta(n^{log_22}) = \Theta(n)$.
$\Rightarrow T(n) \in \Theta (n \log n)$.

### 3b)

$T(n)= 3 T(\frac {n}{3}) + \sqrt{n}$
Es ist Fall 1 erfüllt: $a=3, b=3, f(n)=\sqrt{n}$.
Denn es gilt:
$f(n)=\sqrt(n)=n^{0,5} \in O(n^{(log_33)-\epsilon})=O(n^{1-\epsilon}) =
O(n)$ für $\epsilon = 0,5$
$\Rightarrow T(n) \in \Theta (n^{log_33}) = \Theta (n)$

### 3c)

$T(n)= 2 T(\frac {n}{2}) + \Theta(n^3)$
Es ist Fall 3 erfüllt: $a=2, b=2, f(n)=\Theta (n^3)$.
Denn es gilt:
$f(n)= \Theta (n^3) \in \Omega (n^{(log_22)+\epsilon})=
\Omega (n^{1+\epsilon}) = \Omega (n^{3})$ für $\epsilon = 2$.
Regularitätsbedingung: $af(\frac{n}{b}) \leq cf(n)$ für $c<1$ und alle großen $n$:
$f(n) = \Theta (n^3) \Rightarrow \exists c_1,c_2 > 0, n_0 \in \mathbb{N}_0:
c_1f(n)\leq n^3 \leq c_2 f(n)$
Abschätzen von $T(n)$ nach unten und oben gegen $T'$
und $T''$ mit $T'(n)=2T(\frac{n}{2})+c_1 n^3$
und $T''(n)=2T(\frac{n}{2})+c_2 n^3$.
$c_1,c_2:=d$
$\Rightarrow af(\frac{n}{b})=
2f(\frac{n}{2})=2\frac{dn^3}{2^3}=\frac{1}{4}dn^3=\frac{1}{4}f(n)$
$0<\frac{1}{4}<1 \Rightarrow$ Die Regularitätsbedingung ist erfüllt.
$\Rightarrow T(n) \in \Theta (n^3)$.

### 3d)

$T(n)= 2 T(\frac {n}{2})+ \frac{n}{\log_2 n}$
Es ist keiner der drei Fälle erfüllbar:
$a=2, b=2, f(n)=\frac{n}{\log_2 n}$.
Fall 1: $f(n) \in \Omega (n^{(log_22)+\epsilon}) = \Omega(n)$
Fall 2: $f(n) \in \Theta (n^{log_22}) = \Theta(n)$
Fall 3: $f(n) \in O(n^{(log_22)-\epsilon}) = O(n)$
Wir definieren $g(n):=n$
Es gilt: $lim_{n \rightarrow \infty}\frac{f(n)}{g(n)}=
lim_{n \rightarrow \infty}\frac{\frac{n}{\log_2 n}}{n}=
lim_{n \rightarrow \infty}\frac{1}{\log_2 n}=0$
$\Rightarrow f(n) \in o(n) \Rightarrow f(n) \notin \Omega(n)
\Rightarrow$ Fall 1 ist nicht erfüllt.
Angenommen, es existiert $\epsilon$ mit $f(n) \in O(n^{1-\epsilon})$.
Dann gilt $lim_{n \rightarrow \infty}\frac{\frac{n}{\log_2 n}}{n^{1-\epsilon}}=
lim_{n \rightarrow \infty}\frac{n^{\epsilon}}{\log_2 n}=
lim_{n \rightarrow \infty}\frac{\frac{n^{\epsilon}}{1}}{\log_n 2}=
lim_{n \rightarrow \infty}\frac{n^{\epsilon}}{\log_n 2}=\infty$
$\Rightarrow f(n) \in \omega(n) \Rightarrow f(n) \notin O(n)
\Rightarrow$ Fall 3 ist nicht erfüllt. Damit ist auch Fall 2 nicht erfüllt.
Rekursionsbaummethode:

| Ebene Nr. | Anzahl Knoten | Beitrag (Ebene) |
| --------- | -------------- | ----------------------------------------------------------------------------------------------------------- |
| $0$ | $2^0=1$ | $\frac{n}{\log_2 n}$ |
| $1$ | $2^1=2$ | $\frac{n}{\frac{2}{log_2\frac{n}{2}}}=\frac{n}{\frac{2}{log_2(n)-log_2(2)}}=\frac{n}{\frac{2}{log_2(n)-1}}$ |
| $2$ | $2^2=4$ | $\frac{n}{\frac{4}{log_2\frac{n}{4}}}=\frac{n}{\frac{4}{log_2n-2}}$ |
| ... | ... | ... |
| $i$ | $2^{i}$ | $\frac{n}{\frac{2^i}{log_2\frac{n}{2^i}}}=\frac{n}{\frac{2^i}{log_2(n)-i}}$ |
| ... | ... | ... |
| $log_2n$ | $2^{log_2n}=n$ | $n\cdot T(1) = n$ |

$T(n)= n+ \sum_{i=0}^{(log_2n)-1}\frac{n}{\frac{2^i}{log_2(n)-i}}=
n+ n \sum_{i=0}^{(log_2n)-1}\frac{1}{\frac{2^i}{log_2(n)-i}}=
n+ n \sum_{i=0}^{(log_2n)-1}\frac{1}{2^i(log_2(n)-i)}$
$2^i$ und $i$ sind in jedem Summendurchlauf Konstanten
und dürfen deshalb für die Laufzeitberechnung vernachlässigt werden.
$\Rightarrow T(n)= n+ n \sum_{i=0}^{(log_2n)-1}\frac{1}{log_2(n)}=
n+ n \frac{log_2n}{log_2n}=n+n$
$\in \Theta(n))$

## Aufgabe 4

$A= [9,0,4,10,8,-2,11,16,4,14]$

1. Durchgang $[9, 0, 4, 16, 14, −2, 11, 10, 4, 8]$
2. Durchgang $[9, 16, 11, 0, 14, −2, 4, 10, 4, 8]$
3. Durchgang $[9, 16, 11, 10, 14, −2, 4, 0, 4, 8]$
4. Durchgang $[16, 9, 11, 10, 14, −2, 4, 0, 4, 8]$
5. Durchgang $[16, 14, 11, 10, 9, −2, 4, 0, 4, 8]$

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