Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$
If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align*}
T(\beta) &amp;= 2T(\beta/2) + M(\beta)&amp;\text{given}\\
T(\beta) &amp;= 2T(\beta/2) + \log \beta&amp;\text{given (1)}\\
T(\beta) &amp;= 2\beta - \log (\beta) - 2&amp;\text{inductive hypothesis (2)}\\
T(\beta) &amp;= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&amp;\text{substitute (2) into (1)}\\
T(\beta) &amp;= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&amp;\text{algebra}\\
T(\beta) &amp;= 2\beta - \log (\beta) -2&amp;\text{QED}\\
\end{align*}

So we've proven that if $M(\beta) = \log \beta$ then $T(\beta) = O(\beta)$. However the assignment claims $O(T(\beta)) = M(\beta)\log \beta = \log^2 \beta$. This cannot be true.



If we read between the lines it seems implied that $M = Ω(\beta)$.