# Code and time complexity of multiplication à la française

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.

This is the code given for it.

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.

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?

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

• 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. Feb 14 at 19:33
• I’m not familiar with this algorithm, so cannot answer. Feb 14 at 19:35