TU Wien:Mathematik 2 UE (diverse)/Übungen SS07/Beispiel 142

Beim Sortieren von $n$ Zahlen durch "Direktes Einfügen" gilt für die Anzahl der $v_n$ der Vergleiche (im ungünstigsten Fall)

$v_1=0$ und $v_n=v_{n-1}+n-1$, $n=2,3,\dots$

und für die Zahl $w_n$ der Wertzuweisungen

$w_1=0$ und $w_n=w_{n-1}+n+1$, $n=2,3,\dots$

Warum? Man bestimme explizite Formeln für $v_n$ und $w_n$ und schätze deren Größenordnungen (in der O-Notation) ab.

Links

• Diskussion im Informatik-Forum SS07 Beispiel 142