2
$\begingroup$

This references the multiplication algorithm in Chapter 1 of Algorithms by Dasgupta et al.

I am trying to understand how the code for multiplication à la française works from the multiplication by hand. This is the example given.

by hand

This is the code given for it.

code

I went ahead and did multiplication of $13 \times 11$ (odd) case and $13 \times 10$ (even) in a spreadsheet and this is what I got.

spreadsheet example

It seems to me that in the code the rows of the columns are flipped with respect to handwritten example, that is, in $13 \times 11$, the 1 shows up where 13 is and not where 104 is as in the handwritten example. I still get the correct answer. Where did I make a mistake? In the evaluation or understanding the conversion from handwritten algorithm to algorithm in code.

I also have trouble seeing how to get $O(n^2)$ for the time complexity. I understand that there is bit shifting and addition and so at some point, assuming both $x$ and $y$ are n bits, we end up adding $1 + 2 + 3 + \dots + n = \frac{n}{2}(n+1) = O(n^2)$ but aren't we shifting the bits $n$ times and therefore need to multiply by another factor of $n$ to get $O(n^3)$?

This is what I get when I think of the equation for master theorem: $T(n) = T(\frac{n}{2}) + O(n)$ because there is 1 recursive call and the problem is halved and it takes $O(n)$ time to add n bits. However, this equation would give me $\Theta(n)$ which is wrong. What step did I miss in the recurrence equation?

$\endgroup$
1
$\begingroup$

In the function $T(n)$, the parameter $n$ represents the length of the input in bits. The recursive call reduces $y$ to $\lfloor y/2 \rfloor$, which reduces the length of the input by a single bit. Hence the recurrence is really $T(n) = T(n-1) + O(n)$, whose solution is indeed $T(n) = O(n^2)$.

$\endgroup$
2
  • $\begingroup$ Is the order of the operations flipped though between the handwritten approach and the recursive one in the pseudcode? I am not saying that it doesn't work. Just different order. $\endgroup$ – heretoinfinity Feb 14 at 19:33
  • $\begingroup$ I’m not familiar with this algorithm, so cannot answer. $\endgroup$ – Yuval Filmus Feb 14 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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