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=0und{v}_n=v_{n-1}+n-1,n=2,3,\mathrm{...}$

und für die Zahl $w_n$ der Wertzuweisungen

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

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