====== خیمه‌ی پارسا روی بچه‌ها ======
فرض کنید یک جایگشت مانند
$\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)$ را بیابید.
  

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]