Posted by: atri | September 14, 2012

## Lect 8: What is an Efficient algorithm?

In today’s lecture, we finished proving the correctness of the Gale-Shapley algorithm and then we discussed what our notion of an efficient algorithm is. A lot of reading material was assigned today: Sections 1.1, 1.2, 2.1, 2.2 and 2.4 in the textbook. Since you guys have seen asymptotic notation before, I am going to do a quick review on Wednesday (remember we are off on Monday due to Rosh Hashanah) and Zihe will cover the material in more detail in her recitations next week (but remember no recitation on Monday either). So I will mostly talk about Sec 2.2 in the book and talk a bit about what it means to say that the run time of an algorithm is e.g. $O(n^2)$ or is e.g. $\Omega(n^2)$. In particular, I plan to go through the run time analysis of a simple algorithm.

The slides for todays’ lecture have been uploaded.