$M$ is a set of men and $W$ is a set of women.
Initially all m in M and w in W are free While there is a man m who is free and hasn’t proposed to every woman Choose such a man m Let w be the highest-ranked woman in m’s preference list to whom m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m' If w prefers m' to m then m remains free Else w prefers m to m' (m, w) become engaged m' becomes free Endif Endif Endwhile Return the set S of engaged pairs
Claim: The algorithm above terminates after at most $n^2$ iterations of While loop.
Proof: In the case of the present algorithm, each iteration consists of some man proposing (for the only time) to a woman he has never proposed to before. So if we let $P(t)$ denote the set of pairs $(m, w)$ such that $m$ has proposed to $w$ by the end of iteration $t$, we see that for all $t$, the size of $P(t + 1)$ is strictly greater than the size of $P(t)$. But there are only $n^2$ possible pairs of men and women in total, so the value of $P(\cdot)$ can increase at most $n^2$ times over the course of the algorithm. It follows that there can be at most $n^2$ iterations.
$P(t)$ contains at least $1$ and at most $n^2$ elements. Correct?
$P(t)$ is the set after $t$ iterations and $P(\cdot)$ is the set after unknown number of iterations? I mean $P(t)$ is special case of more general $P(\cdot)$, correct? Else what is $P(\cdot)$?
What's the point of mentioning $|P(t)| < |P(t +1)|$ for all $t$?