es geht um die folgende Umwandlung einer Rekursiongleichung die ich nicht ganz verstehe:
$$Q(n)\quad =\quad \begin{cases} c,\quad \quad für\quad n\quad \epsilon \left\{ 0,1 \right\} \quad \\ cn\quad +\quad \frac { 1 }{ n } \quad \sum _{ i=1 }^{ n }{ (Q(i-1)\quad +\quad Q(n-1)\quad für\quad n\quad >1 } \end{cases}$$
Im Skript wird behauptet: für alle n ≥ 2 gilt die Identität:
$$Q(n)\quad =\quad cn\quad +\quad \frac { 2 }{ n } \quad \sum _{ i=1 }^{ n }{ Q(i-1) } $$
Wieso ist das so?
PS: es handelt sich um die Laufzeitanalyse von Quicksort
