In welk typisch geval heeft quicksort tijdcomplexiteit O(n²)?

Antwoord: C. De gegevens zijn al gesorteerd en het eerste element wordt altijd als pivot gebruikt

Quicksort verdeelt de elementen in elementen die kleiner en elementen die groter zijn dan de pivot, en verdeelt elk deel daarna opnieuw. Zijn de gegevens al gesorteerd en is het eerste element altijd de pivot, dan is de pivot elke keer het minimum en is elke verdeling scheef, met nul elementen aan de ene kant en alle overige aan de andere. Er zijn dan n(n−1)/2 vergelijkingen nodig (4950 voor n = 100). Wordt de pivot willekeurig gekozen of als de mediaan van drie waarden, dan wordt een lange reeks scheve verdelingen uiterst onwaarschijnlijk. Het aantal gegevens speelt voor de tijdcomplexiteit geen rol.