Millä tavalla lajittelua voidaan suorittaa enintään n2:ssa ajassa? Kirjoita edellisen kysymyksen perusteella tekstiyhteys, joka sisältää vastauksen. Se voi olla 1 - 20 lausetta. - Mitä tarkoitat?
Harkitse esimerkiksi deterministista lajittelua, nimeltään quicksort. Tämä ratkaisee ongelman, joka koskee kokonaisten lukujen luettelon lajittamista syöttönä. Pahin tapaus on, kun syöttö on lajiteltu tai lajiteltu käänteisessä järjestyksessä, ja algoritmi kestää aikaa O ((n2) tässä tapauksessa. Jos oletamme, että kaikki mahdolliset syöttöluettelon permutaatiot ovat yhtä todennäköisiä, lajittelun keskimääräinen aika on O ((n log n). Paras tapaus tapahtuu, kun jokainen kiertäminen jakaa luettelon puoliksi, myös tarvitsemalla O ((n log n) aikaa.