시험 직전 요약장

O(n) 알고리즘이 작은 입력에서 항상 O(n log n)보다 빠른 것은 아니다. 그러나 n이 충분히 커질 때 증가율의 차이가 지배적이 된다. 또한 평균 복잡도는 입력 분포 가정이 필요하다.

같은 알고리즘도 입력 상태에 따라 수행 시간이 달라질 수 있다. 예를 들어 퀵정렬은 평균 O(n log n)이지만 피벗 분할이 계속 불균형하면 O(n²)이 된다.