퀵 정렬에서 피벗이 평균적으로 배열을 비교적 균형 있게 분할한다고 할 때 n개 원소 정렬의 평균 시간복잡도는?

1. 1

   O(1)

   오답 이유O(1)은 입력 크기와 무관한 연산 수를 뜻하지만 퀵 정렬은 모든 원소를 비교·분할해야 한다.
2. 2

   O(log n)

   오답 이유O(log n)은 균형 분할의 재귀 깊이만 센 값으로 각 깊이의 Θ(n) 분할 비용을 누락했다.
3. 3

   O(n log n)

   정답 근거평균적으로 Θ(log n) 깊이마다 Θ(n)의 전체 분할 작업이 있어 Θ(n log n)이므로 정답이다.
4. 4

   O(n^3)

   오답 이유O(n³)은 퀵 정렬의 평균·최악 복잡도 어느 쪽에도 해당하지 않는다. 최악은 O(n²)이다.