Độ phức tạp trường hợp nào được biểu diễn khi mỗi trục chia danh sách theo phần ba, cũng cần thời gian O (n log n)?
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).