2.3 Implementing The Stable Matching Algorithm using Lists and Arrays

To asymptotically analyze the running time of an algorithm, we don't need to implement and run it, but we definitely have to think about how the data will be represented and manipulated in an implementation of the algorithm so we could bound the number of computational steps it takes. This section looks at how to implement the Gale-Shapley algorithm using lists and arrays. In the Stable Matching Problems that the algorithm solves, we need to think about how the rankings will be represented, as each man and each woman has a ranking of all members of the opposite gender. In addition, we will need to know which men and women are free, and who is matched with whom. Finally, we need to decide which data structures to use for all of the mentioned data. The goal of for the designer is to choose data structures that will make the algorithm efficient and easy to implement.

Let's focus on a single list, such as a list of women in order of preference by a single man.

• The simplest way to keep a list of n elements is to use an Array A of length n.
• In such an array, let A[i] be the i^th element of the list
• With such an array we can:
• Determine the i^thelement on the list in O(1) time,by accessing the value A[i]
• Determine if a given element e belongs to the list by checking the elements one by one in O(n) time, assuming we don't know the order in which the elements are arranged in A.
• Determine if the given element e belongs to A in O(logn) if A is sorted