Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 3 / d / Solution

A stronger exact formula makes the induction explicit:For $n=1$, the recurrence gives $S_1=S_0+m=1+m$. For $n\ge 2$, set $j=\lfloor n/2\rfloor$, so $1\le j<n$. In the relevant binary interval, $\lfloor {\log }_{2}j\rfloor =\lfloor {\log }_{2}n\rfloor -1$. The strong induction hypothesis givesFor $n\ge 2$, $S_n\le 1+m+m{\log }_{2}n\le (1+2m){\log }_{2}n$. Hence $S_n=O({\log }_{2}n)$. This is an integer-halving recurrence with constant toll; the separately defined $n=0$ case does not require evaluating $\log 0$.