Der Euklidische Algortihmus berechnet den ggT mittels rekursiven Aufrufen¹ folgendermaßen:

$\begin{displaymath}ggT(x,y)=ggT(y,x\,\,mod\,\,y)\end{displaymath}$

Hierbei werden alle Faktoren, die nicht Primfaktoren beider Zahlen sind, herausgezogen, bis letztendlich $ggT(\sum Primfaktoren,0)$ übrigbleibt.

Der Worst-Case-Fall des Euklidalgorithmus sind die Fibonaccizahlen. Die Fibonaccizahlen haben die Eigenschaft, daß wenn man den Rest von $F_{k}/F_{k-1}$ bestimmt, $F_{k-2}$ herauskommt, da $F_{k}=F_{k-1}+F_{k-2}$ . Es müssen somit genau

Schritte durchgeführt werden, um darauf zu kommen, daß der ggT zweier Fibonaccizahlen, die im Wort-Case aufeinander folgen,

ist.
Für Fibonaccizahlen gilt

$\begin{displaymath}F_{k}\geq (\frac{3}{2})^{k-1}\end{displaymath}$

Wir sehen, daß je größer die Zahlen werden, die Häufigkeit der Fibonaccizahlen logarithmisch abnimmt, da die Größe der Fibonaccizahlen exponentiell steigt. Somit gilt $O(\log{n})$ .

Binäre Suche

$\begin{displaymath}T(n)=\Biggl \{\begin {array}{ll} 0&f\uml {u}r\, n\leq 0\\ 1&... ...T(\lfloor\frac{n+1}{2}\rfloor-1)&f\uml {u}r\,n>1\\ \end{array}\end{displaymath}$

$\begin{displaymath}T(n)=1+T(\lfloor\frac{n+1}{2}\rfloor-1)\leq 1+T(\lfloor\frac{n}{2}\rfloor)\end{displaymath}$

1.Fall:

ist eine Zweierpotenz, etwa $2^{k}$

	$=T(2^{k})\leq 1+ T(\frac {2^k}{2})$
	$=1+T(2^{k-1})$
	$\leq 1+1+T(2^{k-2})=2+T(2^{k-2})$
	$\leq...\leq r+ T(2^{k-r})=_{r=k}k+T(2^{0})=k+1$

2.Fall:

beliebig: Sei $2^{k-1}<n<2^{k}$ $(\rightarrow k=\lceil log(n) \rceil)$
$T(n)\leq T(2^{k})\leq k+1=\lceil log(n) \rceil +1 = O (log(n))$

Mergesort

$T(n)=n+T(\lfloor\frac{n+1}{2}\rfloor)+T(n-\lfloor\frac{n+1}{2}\rfloor)\leq n+2*T(\lfloor\frac{n+1}{2}\rfloor)\approx n+2*T(\lfloor\frac{n}{2}\rfloor)$

1. Fall $n=2^{k}$ :

$T(2^{k})$	$=2^{k}+2T(\frac{2^{k}}{2})$
	$=2^{k}+2T(2^{k-1})$
	$\leq 2^{k}+2(2^{k-1}+2T(2^{k-2})$
	$\leq 2*2^{k}+2^{2}T(2^{k-2})$
	$\leq...\leq r2^{k}+2^{r}T(0)$
	$=r*2^{k}$
	$=_{r=k}k*2^{k}$
$\Rightarrow$