Reading

These notes and closely review Unit 2 Section 3.

Quiz questions

• P4 from Week 04 quiz questions (take home, to be done before Class 11)
• P5 from Week 04 quiz questions (take home, to be done before Class 11)

Finishing off lower bounds

We finished off our proof that for any comparison-based sorting algorithm, the worst case running time is $\Omega(n \lg n)$.

Sorting review

We reviewed the sorting algorithms we know and their running times: selection sort, insertion sort, merge sort, heap sort. We also reviewed the limitations of our analysis, e.g. "is it true that for any input array, merge sort is faster than selection sort?". Why is the answer "no"?

Reviewing sorting

Midn X suggested an improvement to mergesort that he hypothesized would make its best case $\Theta(\lg n)$. The improvement is to add

if A[m] \le; A[m+1] return

to the top of "merge". When the original input is already sorted, this will make all the merge's take constant time. This gave us a great opportunity to analyze a recursive algorithm. We also discussed that this hypothesis is impossible, because any correct sorting algorithm must at least examine every element in the array, so any sorting algorithm has a best case running time that is $\Omega(n)$.