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