York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 4:

1.Lower bound for comparison sorting algorithms [Section 8.1]
The main idea is to associate each comparison-based sorting algorithm
with a decision tree. The height of the tree is a lower bound for the
worst-case running time of the algorithm.
The height of the tree is shown to be "big" (Omega(nlogn)), using the
fact that the tree has "many" leaves (i.e. at least n!).


2. Counting-sort and Radix-sort [Section 8.2, 8.3]