In Algorithm Design by John Kleinberg and Eva Tardos, the proof for the Gale-Shapley algorithm running in $O(n^2)$ is given
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(.) can increase at most $n^2$ times over the course of the
algorithm. It follows that there can be at most $n^2$ iterations.
Few questions:
- What are we actually proving? I find it strange we are proving the running time is $O(n^2)$ because that's something we usually don't actually prove.
- What does $.$ mean in $P(.)$?
- I never actually defined what $n$ is but I'm assuming it's the number of men i.e. $|M|$?
- I don't accept the statement "we see that for all t, the size of P(t + 1) is strictly greater than the size of P(t)" because if $m$ purposes to $w$ and $w$ was engaged to $m'$ but leaves $m'$ for $m$, then there the number of pairs hasn't gone up. Strictly greater than means it can't be equal (ie no change), right?
- Isn't this proof just saying "since there are $n \times n$ ways to match elements from one set of size $n$ to another set of size $n$, the running time is at most $O(n^2)$
Best Answer
What is it that you usually do?
Anything, basically any value of $t$. The $.$ is a common placeholder for a variable that you don't want to name.
Yes.
$P(t)$ is the number of proposals made by time $t$, not proposals accepted. If no new proposals are made, then the algorithm is finished.
There are $n!$ ways to match elements from one set of size $n$ to another set of size $n$. There are $n^2$ ways of matching one element of a set of size $n$ to an element of another set of size $n$.