TU Wien:Mathematik 2 UE (diverse)/Übungen SS06/Differenzengleichungen 24

Angabe

Beim Sortieren von n Zahlen durch „Direktes Einfügen“ gilt für die Anzahl $v_{n}$ der Vergleiche (im ungünstigsten Fall)

$v_{1}=0\;und\;v_{n}=v_{n-1}+n-1,n=2,3,...$

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

$w1=0\;und\;w_{n}=w_{n-1}+n+1,n=2,3,...$.

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

Quelle

Karigl Beispielsammlung SS04 Beispiel 28