یک جایگشت دلخواه از اعداد ‎$1,2,\ldots,n$‎ را می‌خواهیم با عمل «وارون‌ساز» مرتب کنیم. عمل وارون‌ساز به عملی می‌گوییم که در طی آن یک زیر دنباله از جایگشت انتخاب می‌کنیم و اعضای آن را وارون می‌کنیم. فرض کنید ‎$f(n)$‎ کمترین تعداد عمل وارون‌ساز لازم برای یک جایگشت دلخواه از ‎$1,2,\ldots,n$‎ باشد. مثلا برای جایگشت ‎$3,5,1,4,2$‎ این عدد برابر ‎$2$ است. زیرا کافیست در گام اول زیر دنباله‌ی ‎$3,1$‎ را انتخاب کنیم و به جایگشت ‎$1,5,3,4,2$‎ برسیم و در گام دوم زیردنباله‌ی ‎$5,4,2$‎ را انتخاب کنیم و به جایگشت مرتب شده برسیم.

1. ثابت کنید ‎$f(n) \in \Omega(\log n)$‎
2. ثابت کنید ‎$f(n) \in O(\sqrt{n})$‎

• سوال قبل