Talk:Stable roommates problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Complexity[edit]

Someone should add the runtime complexity of the algorithm to find matches so I know if it's worth looking up the paper.

Runtime complexity now appears, together with a descriprion of the algorithm and an example of its execution. RobWIrving (talk) 12:55, 23 September 2010 (UTC)

Error in the example[edit]

The text explains how in Phase 2, a chain of odd length means that there is no stable pairing. On the other hand, the example ends with a stable pairing after some rotations, one of them of length 3. It's easy to check that that chain is not correct. — Preceding unsigned comment added by Davidsevilla (talkcontribs) 15:10, 29 June 2011 (UTC)

O(n^2)[edit]

What is O(n^2)? It is written like it's common knowledge, however I'm pretty certain it's not. IMO encyclopædia should not assume previous knowledge. At least there should be a link an explanatory page. --Kebman (talk) 20:39, 6 January 2013 (UTC)