In class we proved that the runtime of the Gale-Shapely algorithm is O(n). In this question...

Transcribed Image Text:

In class we proved that the runtime of the Gale-Shapely algorithm is O(n²). In this question you will prove that this bound is tight. That is, that there is a matching (n²) lower bound - there exists c, no > 0 such that for all n ≥ no, there is an instance of Stable Matching with n people and n supervisors such that the runtime of the Gale-Shapely algorithm on this algorithm takes time at least cn². (a) (7pts) Let n be an arbitrary integer which is at least no. Describe an instance of Stable Matching (that is, a list of preferences) which requires the Gale-Shapely algorithm time at least cn². Hint. Think about what would cause the Gale-Shapely algorithm to un-match each person a large number of times. 1 (b) (8pts) Prove that the instance that you described in (a) requires time cn². In class we proved that the runtime of the Gale-Shapely algorithm is O(n²). In this question you will prove that this bound is tight. That is, that there is a matching (n²) lower bound - there exists c, no > 0 such that for all n ≥ no, there is an instance of Stable Matching with n people and n supervisors such that the runtime of the Gale-Shapely algorithm on this algorithm takes time at least cn². (a) (7pts) Let n be an arbitrary integer which is at least no. Describe an instance of Stable Matching (that is, a list of preferences) which requires the Gale-Shapely algorithm time at least cn². Hint. Think about what would cause the Gale-Shapely algorithm to un-match each person a large number of times. 1 (b) (8pts) Prove that the instance that you described in (a) requires time cn².

Answer rating: 100% (QA)

a To create an instance of Stable Matching that requires the GaleShapely algorithm to take time at l... View the full answer