*Marius* Nu ar fi mai bine ca O(N^2^) 20p, O(N logN) 50p, O(N logK) 60-70, O(N) 100? Când atinge O(N^2^) algoritmul O(N)?
*Paul:* Parca am citit pe undeva ca $nth_element$ din STL are complexitatea worst case $O(NlogN)$. E si suspect sa mearga sort-ul worst case $O(NlogN)$ si statisticile de ordine $O(N^2)$. Verifica acest fapt.

*Mishu:* "Timpul de execuţie, în cazul cel mai defavorabil este $O(N^2^)$, pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. [...] Deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz." -> Cormen. De aici, probabil se trage faptul că în cel mai defavorabil caz complexitatea se aproximează $O(NlogN)$. Cât despre soluţii, am să modific unele teste astfel încât soluţia în $O(NlogN)$ să ruleze mai slab decât cea în $O(NlogK)$.

h3. Aplicaţii