Per esempio, si consideri l' algoritmo di ordinamento deterministico quicksort. Questo risolve il problema di ordinare un elenco di numeri interi che viene dato come input. Il caso peggiore è quando l' ingresso viene ordinato o ordinato in ordine inverso, e l' algoritmo richiede tempo O (n2) per questo caso. Se si suppone che tutte le possibili permutazioni dell' elenco di input siano ugualmente probabili, il tempo medio impiegato per lo smistamento è O (n log n). Il caso migliore si verifica quando ogni rotazione divide l' elenco a metà, richiedendo anche O (n log n) tempo.
Quando c' è bisogno di molto tempo per ordinare gli interi, questo rappresenta la complessità del caso?
caso peggiore peggiore caso peggiore