====== سوال ۲ ======

یک ماشین $k$-خفن ماشینی است که اگر $k$ عنصر متوالی از یک آرایه را به آن بدهیم آن را در $Ο(1)$ مرتب می‌کند.

  - ثابت کنید به‌ازای $k=c>1$ (یعنی یک عدد ثابت) مرتب کردن یک آرایه با اندازه $n$ بوسیله یک ماشین $k$-خفن در بدترین حالت از $Ω(n^2)$ می‌باشد. دقت کنید در این قسمت و قسمت بعد ما به خود آرایه دسترسی نداریم و فقط می‌توانیم ماشین را کنترل کنیم.
  - ثابت کنید که به ازای $k=n/c$ مرتب کردن یک آرایه به طول $n$ از $Ο(c^2)$ است.

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]