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,\ldots$

und für die Zahl $w_{n}$ der Wertzuweisungen

$w_{1}=0$ und $w_{n}=w_{n-1}+n+1$, $n=2,3,\ldots$

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