York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary and References for Lecture 2:

1. Recall of the big-O, big-Omega and Theta notations from
the previous lecture.
Introduce the little-o and little-omega notations. [Section 3.1]

Some examples, including log(n) = o(n) and nlog(n) = o(n^2).


2. The Heapsort algorithm [Reference Sections 6.1-6.4]

3. Mergesort and Divide-and-Conquer technique [Section 2.3]

4. The Master Theorem [Section 4.3] and its proof follows from
Assignment 1 -- See also Section 4.4.