Điều gì cung cấp một giải pháp cho một danh sách các số nguyên được cung cấp làm đầu vào mà ned sẽ được sắp xếp?
Ví dụ, xem xét các thuật toán sắp xếp tất định quicksort. Điều này giải quyết vấn đề sắp xếp một danh sách các số nguyên được đưa ra như là đầu vào. Trường hợp xấu nhất là khi đầu vào được sắp xếp hoặc sắp xếp theo thứ tự ngược lại, và thuật toán mất thời gian O(n2) cho trường hợp này. Nếu chúng ta giả định rằng tất cả các hoán vị có thể có của danh sách đầu vào đều có khả năng như nhau, thời gian trung bình để sắp xếp là O(n log n). Trường hợp tốt nhất xảy ra khi mỗi pivoting chia danh sách làm đôi, cũng cần thời gian O(n log n).
Thuật toán sắp xếp xác định Quicksort