Laufzeit rekursiver Programme (II)

linear:

		L(0) = 0
n > 0	$\displaystyle \Rightarrow$	L(n) $\displaystyle \le$ 1 + L(n - 1)

Wertetabelle?

Lösung: L(n) $\le$ n.

binär

		B(0) = 0
n > 0	$\displaystyle \Rightarrow$	B(n) = 1 + B( $\displaystyle \lfloor$ n/2 $\displaystyle \rfloor$ )

Wertetabelle?

Lösung: B(n) = $\lfloor$ log₂(n + 1) $\rfloor$

Johannes Waldmann 2009-01-12