ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น 2 n 2 {\displaystyle 2n^{2}}

สมมติฐาน :

1. สมมติฐานที่ 1: ฝ่ายชายขอแต่งงานกับฝ่ายหญิงด้วยลำดับความพึงพอใจที่ลดลงจากมากไปน้อย
2. สมมติฐานที่ 2: ฝ่ายหญิงที่ทำการหมั้นไปแล้วครั้งหนึ่ง จะไม่มีทางที่จะไร้คู่สมรสเพราะเธอจะไม่ถอนหมั้นก็ต่อเมื่อไม่เจอฝ่ายชายที่เลือกตนและตนพึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราว

การแก้ปัญหาแบบถึก (Brute-force) :

• เวลาที่ใช้ในการทำงานในกรณีแย่สุดที่ใช้การตรวจสอบรายชื่อทั้งหมด เป็น n ! x {\displaystyle n!x} (เวลาที่ใช้ในการตรวจสอบเสถียรภาพของการจับคู่) เท่ากับ Θ ( n ! n 2 ) {\displaystyle (n!n^{2})}

การพิสูจน์ความถูกต้อง :

1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น n 2 {\displaystyle n^{2}} จากการทำงานของวงวน

• พิสูจน์: จากรายชื่อที่หมายปองทั้งหมดของฝ่ายชายมีจำนวนรูปแบบที่เป็นไปได้ n 2 {\displaystyle n^{2}} รูปแบบ ดังนั้น วงวนจะทำงานเป็นจำนวนครั้งมากที่สุดเท่ากับ n 2 {\displaystyle n^{2}} ครั้ง

2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน

• พิสูจน์โดยหาข้อขัดแย้ง

• สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
  • จะพบ มีนางสาวเอ ไม่มีคู่เช่นกันแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
  • จากสมมติฐานที่ 2 แสดงว่านางสาวเอ ไม่มีฝ่ายชายคนไหนเลยที่ปรารถนาจะแต่งงานด้วยเลย
  • แต่จากปัญหานี้ ฝ่ายชายทุกคนจะทำการเลือกฝ่ายหญิงทุกคน ตามลำดับความพึงพอใจ ดังนั้น นายหนึ่ง ทำการเลือกนางสาวเอ แล้ว
  • ดังนั้นจึงเป็นไปไม่ได้ที่จะมีฝ่ายชายหรือฝ่ายหญิงคนใด ไม่มีคู่

3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ

• พิสูจน์โดยหาข้อขัดแย้ง

• สมมติให้ การจับคู่คู่หนึ่งระหว่างนายหนึ่ง กับนางสาวเอ ขาดเสถียรภาพ ในขณะที่พวกเขาเสนอรายชื่อของกันและกันในรายชื่อที่หมายปอง
  • กรณีที่ 1: นายหนึ่งไม่เคยขอแต่งงานกับนางสาวเอ
    • นายหนึ่งขอแต่งานกับนางสาวเอในที่สุด (จากการลดลำดับความพึงพอใจในรายชื่อที่หมายปองของฝ่ายชาย)
    • การจับคู่ระหว่าง นายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
  • กรณีที่ 2: นายหนึ่งขอแต่งงานกับนางสาวเอไปแล้ว
    • นางสาวเอ ปฏิเสธการขอแต่งงานของนายหนึ่ง (ทั้งกรณีที่นายหนึ่งไม่ดีกว่าคู่หมั้นชั่วคราวของนาวสาวเอ และกรณีที่เลือกนายหนึ่ง ไปแล้ว แต่เจอคนที่ดีกว่าในภายหลัง)
    • แสดงว่านางสาวเอก็เสนอรายชื่อของนายหนึ่ง ในรายชื่อที่หมายปองไว้แล้ว เพียงแต่ต้องการคนที่ดีกว่าเท่านั้น
    • การจับคู่ระหว่างนายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ