Sort Lower Bound

Time Complexity

comparison-based sorting은 time complexity의 lower bound가 O(nlogn)이다.

 

Decision Trees

 

n개의 element가 있는 array가 있을 때 나올 수 있는 permutation의 수는 n!이다. 

sorting algorithm은 이 permutation들 중 올바른 유일한 permutation을 하나 고르는 것이다.

decision tree에서 permutation은 각각의 leaf node에 위치하게 된다.

그렇다면 어떠한 comparison based sorting algorithm은 n!개의 leaves를 가져야 한다.

 

n!개의 leaves를 가지는 tree의 depth는 어떨까?

n개의 node를 가지는 tree의 level은 Ω(logn)이다.

그렇다면 n!개의 leaves를 가지는 binary tree의 depth는 Ω(logn!) = Ω(nlogn)이다.

 

sorting algorithm에서 worst case는 가장 깊은 level에 있는 노드가 선택되는 것이다.

어떤 algorithm이던 깊이가 Ω(nlogn)이기 때문에 worst case는 Ω(nlogn) 이상으로 좋아질 수 없다.