\begin{slide}{Laufzeit rekursiver Programme (I)}

abhängig von den Eingabewerten,
beim Einfügen: von der Länge der Folge.


$L(n)$ die Laufzeit von \verb|linear-einf|
für Eingabefolge der Länge n.

$B(n)$ die Laufzeit von \verb|binär-einf|
für Eingabefolge der Länge n.


\end{slide}


\begin{slide}{Laufzeit rekursiver Programme (II)}

linear:
\begin{eqnarray*}
 && L(0)= 0 \\
n>0 &\Rightarrow& L(n) \le 1+L(n-1)
\end{eqnarray*}

Wertetabelle?

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

\bigskip

binär
\begin{eqnarray*}
 && B(0)= 0 \\
n>0 &\Rightarrow& B(n) = 1+ B( \lfloor n/2 \rfloor  )
\end{eqnarray*}

Wertetabelle?

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

\end{slide}
