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?
Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$
algorithm analysis;asymptotics;recurrence relation;recursion;divide and conquer
The exercise seems fine.  You can take care of those issues with a little more work, by reasoning about what the running time of a multiplication algorithm must look like.One can show that, for any correct multiplication algorithm, we have $M(\beta)=\Omega(\beta)$.  Indeed, any correct algorithm has to read all bits of the input, so the lower bound follows.  Thus, the first case you were worried about, where $M(\beta)=o(\beta)$, can't happen.We can consider two remaining cases:If $M(\beta)= \Theta(\beta \cdot \text{poly}(\log(\beta))$, then by the Master theorem, we have $T(\beta) = \Theta(M(\beta) \log(\beta))$.  This matches the bound proposes in the exercise statement.If $M(\beta) = \Omega(\beta^{1+\epsilon})$ for some $\epsilon>0$, then by the Master theorem $T(\beta)=\Theta(M(\beta))$.  Of course, if you can solve a problem in time $T(\beta)$, you can also solve it in time $T'(\beta)$, if $T'(\beta) \ge T(\beta)$ by padding (just add some extra no-ops).  Consequently, in this case there also exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.In either case, we achieve the claimed result.OK, technically I realize that these don't cover all remaining cases.  But I believe it is still true that once we know that $M(\beta)=\Omega(\beta)$, then it follows that the solution to the recurrence relation satisfies $T(\beta) = O(M(\beta) \log(\beta)$, so there exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.