Hvilken teknik virker bedst, når dens pivoter opdeler input i lige lister? Skriv et svar i sammenhæng med det foregående spørgsmål. Det kan være 1 - 20 sætninger. Kontekst:
For eksempel, overveje den deterministiske sortering algoritme quicksort. Dette løser problemet med at sortere en liste af heltal, der er givet som input. Det værste tilfælde er, når input er sorteret eller sorteret i omvendt rækkefølge, og algoritmen tager tid O ((n2) for dette tilfælde. Hvis vi antager, at alle mulige permutationer af indgangslisten er lige sandsynlige, er den gennemsnitlige tid, der tages for sortering, O ((n log n). Det bedste tilfælde opstår, når hver pivoting deler listen i to, og også har brug for O ((n log n) tid.