Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 8 / c / Solution

The printed split uses $n$ while naming the current length $m=j-i$. For the intended stooge sort, read that split as $k=\lfloor m/3\rfloor$ at every recursive call. Keeping one fixed original $n$ instead is not the standard algorithm and does not generally sort correctly.

The three recursive calls then each have length $m-\lfloor m/3\rfloor =\lceil 2m/3\rceil$, and all other work is constant. ThusA version of the master theorem sufficient here states: if $T(n)=aT(\lceil n/b\rceil )+f(n)$ with constants $a\ge 1,b>1$, fixed-size base cases and $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$, provided the recursive sizes shrink above the base threshold. Apply it with $a=3,b=3/2,f=\Theta (1)$ to obtainThe rounded size is important for correctness; it does not change this asymptotic exponent.