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

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

• سوال بعد
• سوال قبل