How do I achieve O(n^2) complexity for the Gale-Shapley algorithm?

user_13204864 0
Viewed 2653

The Gale-Shapley Algorithm is meant to solve the stable matching problem with O(n2). In the matching problem, there are n women and n men. Each person has a preference list ranking every member of the opposite sex for marriage. The goal is to create couples such that no one would be better off leaving their marriage for someone else.

The following is pseudocode from Wikipedia:

algorithm stable_matching is
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if w is free then
            (m, w) become engaged
        else some pair (m', w) already exists
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged 
            else
                (m', w) remain engaged
            end if
        end if
    repeat

Every man (n) can propose up to n times in the worst case. That gives the while loop O(n^2). But there's a line in the inner loop which concerns me: 

if w prefers m to m' then

Shouldn't this mean we have to iterate through a preference list to find who appears first? Wouldn't that also be O(n), making the algorithm O(n3)?

My preference lists for men and women are both of type int[n][n]. The outer index is the id of the person who owns the inner list. The inner list contains the ids of everyone in the opposite sex, ordered by the owner's preference.

data-structures time-complexity algorithm
3 Answers

Shouldn't this mean we have to iterate through a preference list to find who appears first? Wouldn't that also be O(n), making the algorithm O(n3)?

Nope.

My preference lists for men and women are both of type int[n][n]. The outer index is the id of the person who owns the inner list. The inner list contains the ids of everyone in the opposite sex, ordered by the owner's preference.

What you need to do with the preferences determines the appropriate data structure to use for them. You need a woman to be able to compare her preferences for 2 different men in constant time, so you should use a data structure that supports that. For example you can invert the women's preference lists to create a rank map, so that rank[m] returns the rank of man m in her original list of preferences.

Creating all the rank maps takes O(n2) time (in the number of people), so it doesn't increase the overall complexity of the algorithm.

user_54835260

No. You don't need to iterate to find the preference. Because the preference is given in order. Here, the definition of preference is an order over men or women. Hence, you don't need to iterate to find that m is prefered over m' or not.

user_37688710

You will store the preference list of n males and females in order in an Array. At the stage where you are saying that we will need another loop to go through n men in woman preference list we can avoid this loop by creating a priority based array and just use O(1) time to access the rank.

Of course to do this we need to create a Ranking Matrix or Map or simply an array of nn size. For each woman array will take n space and since there are n women we need nn space, same for men, they will also have n*n space. So we will have space complexity of O(n^2). By creating this ranking matrix in the beginning we are able to skip the loop you are mentioning and able to get time complexity of O(n^2).

As mentioned by Matt above this is possible only by using appropriate Data Structure for this step. You can use any Data Structures where we can access the ith element in linear time for this.

user_155644110
Related