2.3: Implementing the Stable Matching Algorithm Using Lists and Arrays

The runtime of the outside while loop will be at most n^2, but we need to find a way to make all of the other operations within the loop to be O(1) so that the entire algorithm runs at O(n^2) as was shown in chapter 1. In order to do this some cases may involve preprocessing the input to convert it from its given input representation into a data structure that is more appropriate for the problem being resolved.

This chapter then goes into the differences between arrays and linked lists, and the reasoning behind using either. Strong uses of Arrays:

• direct access to values with a given index O(1)
• is x in collection - O(n)
• if sorted, is x in collection - O(logn) (binary)

Strong uses of Linked Lists:

• Deletion - O(1)
• Insertion - O(1)

The Gale-Shapely Algorithm uses a combination of both linked lists and arrays in order to be implemented at its most efficient. This section definitely helped me understand the actual implementation better, look at p 46-47 to see actual implementation. 10/10