Gale Shapley algorithm terminates
This page collects material from Fall 17 incarnation of CSE 331, where we proof details for the claim that the Gale-Shapley algorithm terminates in $O(n^2)$ iterations.
Where does the textbook talk about this?
Section 1.1 in the textbook has the argument (though not in as much detail as below).
Fall 2017 material
Here is the lecture video (it starts from the part where we d the proof details):
Video quality is not the greatest
Apologies for the not so great quality of the video!
Here are the slides: , as well as the handwritten nodes: .
More Information
The support page on progress measure talks about the proof technique that is used above.