Termination

As simple as the algorithm is, its behavior is not immediately obvious.

Let's show that no boy can be rejected by all girls.

This proves Theorem 5: the algorithm terminates before the ROL of any boy is exhausted. We get a marriage!


next up previous
Next: Correctness Up: UNDERSTANDING THE ALGORITHM Previous: UNDERSTANDING THE ALGORITHM