Zeigen Sie, dass Quicksort eine Laufzeit aus Θ(n^2) hat,

Question

wenn eine aufsteigende Folge von n paarweise verschiedenen Zahlen sortiert wird und Quicksort als Pivotelement das letzte Element der Folge wählt.

Answer 1

Dann ist $$T(n)=T(n-1)+T(1)+cn.$$ Kleiner Gauss ergibt $$T(n)=\Theta(n^2).$$