Wir messen den Aufwand von Insertionsort als die Anzahl von Schreibzugriffen auf das Ziel-Array. Es sei $T(n)$ der Aufwand um die ersten $n$ Werte des Arrays zu sortieren.

Führen Sie $T(n)$ per Rekurrenzgleichung auf $T(n-1)$ zurück (den Aufwand, die ersten $n-1$ Werte zu sortieren). Stellen Sie zwei Versionen der Rekurrenzgleichung auf:

• Für den Best Case
• Für den Worst Case.

Lösen Sie beide Rekurrenzgleichungen und bestimmen Sie so die jeweilige Komplexitätsklasse.