Content deleted Content added
Undid good faith revision 1018957387 by 2601:647:5A00:9FA0:B0C0:971:EA91:10E7 (talk). This is part of an argument for why the algorithm must terminate, and your addition makes it use the circular reasoning "it can't happen because if it did the algorithm wouldn't terminate". That is not an improvement. |
m Open access bot: hdl added to citation with #oabot. |
||
Line 23:
* This process is repeated until everyone is engaged.
The runtime complexity of this algorithm is <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite journal|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|title=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|journal=International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008)|isbn=978-0-7695-3128-1|hdl=2433/226940|url=https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/226940/1/ICKS.2008.7.pdf|hdl-access=free}}</ref>
This algorithm guarantees that:
| |||