Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$ The following problem is from CLRS (31.1-13, Page 933, 3rd edition):


  Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $Θ(M(\beta)\log \beta)$. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)


By a simple divide and conquer (by dividing $\beta$-bit integer into two $\beta/2$-bit integers), I obtain the recurrence $T(\beta) = 2T(\beta/2) + M(\beta)$. However, how to argue that it is $O(M(\beta) \log \beta)$? 



My attempt: I think the result relies on $M(\beta)$. If $M(\beta) = \Theta(\beta)$, then $T(\beta) = \Theta(M(\beta)\log \beta)$. But, if, for example, $M(\beta) = o(\beta)$ or $M(\beta) = \omega(\beta^2)$, you may not obtain $T(\beta) = \Theta(M(\beta)\log \beta)$.



According to the hint, it seems that we should use different recursions to obtain $O(M(\beta)\log \beta)$ and $\Omega(M(\beta) \log \beta)$, respectively. But how?
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)$.