Time Analysis

But first, how long does it take for $\mbox{\sc Match}$ to run?

What happens in the while loop? Either a free girl accepts her first proposal or a boy gets rejected. What's an upper bound for each of these?

So, that tells us how many times the loop is executed. How much work do we do per iteration? We need to find a free man and we execute RANK several times. These can both be done in O(n).

This gives us a running time of O(n³).