Onye's Journal

Section 1.1 talked about the stable matching problem and the gale shapely soluition to it. A typical example of the stable matching problem is n men and n women looking to be matched, with each man and woman having a strict order of preferences. For a given matching, m and w form an unstable pair if they each prefer each other to their current partner. For n men and n women with strict preferences, it is always possible to find a matching with no unstable pairs, and the gale shapely algorithm does just that.

Chapter 2 dicusses the computational tractability and the running time of algorithms. It also discusses asymptotic order of growth and Big O. Algorithms that are polynomial time are O(n^k) for some k. These are said to be efficient. As opposed to that, some algorithms may be O(k^n), for some k > 1, for example. These algorithms are incredibly computationally intensive and quickly become impossible to calculate in a reasonable amount of time.