How to understand the recurrence relation and time-complexity of StoogeSort?
Here are some more hints:


The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
When $n=4$, the algorithm sorts $a_1,a_2$, then $a_3,a_4$, then $a_1,a_2$. You can easily give an example showing that this doesn't work.
You should be able to solve this yourself.
The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.
For a permutation $\pi$, the number of inversions is the number of pairs $i&lt;j$ such that $\pi(j)&lt;\pi(i)$. A permutation can have at most $\binom{n}{2}$ inversions (this is the number of pairs $i &lt; j$). Each swap operation reduces the number of inversions by 1.