فرض کنید یک جایگشت مانند $\pi = <\pi_1, \pi_2, \ldots, \pi_n>$ از اعداد $1, 2, \ldots, n$ داریم و می‌خواهیم این جایگشت را مرتب کنیم. به اعداد $1, 2, 4, 8, 16, \ldots$ اعداد یاسی می‌گوییم. در هر مرحله می‌توان یک زیرجایگشت از اعداد متوالی جایگشت انتخاب کرد؛ طوری که تعداد اعداد این زیرجایگشت، یک عدد یاسی باشد؛ سپس اعداد این زیرجایگشت وارونه می‌شوند. برای مثال جایگشت $1, 6, 5, 2, 3, 4$ را می‌توان در ۳ مرحله به شکل زیر مرتب کرد: $$ 1, \underline{6, 5}, 2, 3, 4 \rightarrow 1, 5, \underline{6, 2, 3, 4} \rightarrow 1, \underline{5, 4, 3, 2}, 6 \rightarrow 1, 2, 3, 4, 5, 6 $$ کمینه‌ی تعداد مراحل لازم برای مرتب کردن جایگشت $\pi$ را $f(\pi)$ می‌گوییم. فرض کنید بیش‌ترین مقدار $f(\pi)$ به ازای تمام جایگشت‌های ممکن از اعداد $1, 2, \ldots, n$ برابر $g(n)$ باشد. $\theta \big(g(n)\big)$ را بیابید.

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