2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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))$.

$\endgroup$
  • $\begingroup$ "just add some extra no-ops": This sounds a little bit weird in algorithm analysis. However, it is a possible answer. $\endgroup$ – hengxin Apr 2 '17 at 6:07
1
$\begingroup$

If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align*} T(\beta) &= 2T(\beta/2) + M(\beta)&\text{given}\\ T(\beta) &= 2T(\beta/2) + \log \beta&\text{given (1)}\\ T(\beta) &= 2\beta - \log (\beta) - 2&\text{inductive hypothesis (2)}\\ T(\beta) &= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&\text{substitute (2) into (1)}\\ T(\beta) &= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&\text{algebra}\\ T(\beta) &= 2\beta - \log (\beta) -2&\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)$.

$\endgroup$
  • $\begingroup$ Good observation. But... Multiplication has to read all bits of the input (any correct algorithm has to read the entire input), so it follows that any multiplication algorithm will satisfy $M(\beta) = \Omega(\beta)$, and we can rule out the case you are worried about here. I don't see why the exercise needs to assume that $M(\beta) = O(\beta)$; I don't think that assumption is necessary. $\endgroup$ – D.W. Mar 29 '17 at 6:03
  • $\begingroup$ @D.W. You're assuming a computational model which may or may not apply. Consider hardware multiplication, where you have parallelism for every bit. $\endgroup$ – orlp Mar 29 '17 at 6:07
  • $\begingroup$ @D.W. I corrected an error in my answer, I had written $M = O(\beta)$ instead of $M = Ω(\beta)$. $\endgroup$ – orlp Mar 29 '17 at 6:13
  • 1
    $\begingroup$ OK, good point, I overlooked that other models of computation might be possible! But isn't that usually assumed implicitly: when we talk about a problem taking time $T(n)$, that usually implicitly refers to sequential RAM machine algorithms, unless otherwise noted, doesn't it? Do you agree? $\endgroup$ – D.W. Mar 29 '17 at 6:13
  • $\begingroup$ @D.W. I definitely agree and if anything my answer is trying to be 'too clever'. $\endgroup$ – orlp Mar 29 '17 at 6:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.