Section 2.3 Implementing the G-S Algorithm
Analytically, we have found that the Gale-Shapley stable matching algorithm can run in O(n2) time. This is the result of the loop that drives the progress of the algorithm running in O(n2) time, which means that each step within the loop must run in constant time. Our task, then, is to determine which data structures to implement in order to support this constant time execution of steps within the loop.
The first step in deciding which data structures to implement is identifying what will be happening in each instruction within the loop: 1) choosing a free man; 2) for a man m, find the highest-ranked woman to whom he has not yet proposed; 3) for a woman w, find if she is engaged and if so, identify her current partner; 4) find which man, m or m' that a woman w prefers.
