Held: Wednesday, 7 October 2015

Back to Outline 17 - Heap Sort. On to Outline 19 - O(n) Sorting Algorithms.

Summary

We consider lower bounds on comparison-based sorting algorithms.

Related Pages

Overview

• Compare-and-swap algorithms.
• Decision trees.
• Analyzing the size of these decision trees.
• Estimating n!.

Administrivia

• No class on Friday, October 16
• PMO on Wednesday, October 14

Upcoming Work

• For Friday: Chapter 4 of Skiena
• For next Wednesday: Exam 1

Extra Credit

• Don't forget that you can send these to me in advance!

Academic

• CS Table Tuesday at noon: NSA Barbie
• CS Table Thursday: Blake

Peer

Lower Bounds, Revisited

• I was reminded that the better way to do the analysis of O(n!) is to think about the value of log(n!).
• log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1)
• Can you use that to determine an upper bounds using O(...) and a lower bound using Omega(...)?