최선, 최악, 그리고 평균의 경우: 두 판 사이의 차이

* [[삽입 정렬]] 리스트에 ''n''개의 모두 다른 원소가 있고 초기 랜덤 순서로 나열되어 있다고 가정하자. 평균적으로 리스트의 ''A''₁ ... ''A''_''j'' 까지 절반의 원소들은 ''A''_''j''+1 보다 작은 값을 가지고 절반은 큰 값을 가진다. 그러므로 알고리즘은 (''j'' + 1)번째 원소와 평균적으로 절반의 이미 정렬된 서브-리스트(sub-list)가 비교하며''t''_''j'' = ''j''/2 가 된다. 계산 결과 평균 경우 실행 시간은 최악의 경우 실행 시간과 비슷하게 입력 크기에 대한 이차 함수 형태이다.

* [[퀵 정렬]] 위와 동일하게 리스트에 ''n''개의 모두 다른 원소가 있고 초기 랜덤 순서로 나열되어 있다고 가정하자. 퀵 정렬은 평균 경우 성능이 O(''n'' log(''n''))이며 실제로 이는 매우 빠른 [[정렬 알고리즘]]에 속한다. 그러나 최악의 경우 입력이 주어졌을 경우, 성능이 O(''n''²) 까지 저하된다. 또한 “가장 짧은 것 먼저(shortest first)” 방법으로 구현되지 않았다면, 최악의 경우 공간 복잡도(worst-case space complexity)는  O(log(''n''))로 성능이 저하된다.