یک جایگشت دلخواه از اعداد $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})$