Content deleted Content added
Undid revision 1023488252 by 88.103.239.214 (talk) n^2 IS LINEAR IN THE INPUT SIZE, because the input size is n^2. |
→Solution: Clarify for editors like the previous IP who miss the point |
||
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> Since the input preference lists also have size proportional to <math>n^2</math>, the runtime is linear in the input size.
This algorithm guarantees that:
| |||