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$log2(n + 1)$ \rfloor$



Johannes Waldmann 2009-01-12