Question

How long does the recursive multiplication algorithm (page 25) take to multiply an n -bit number by an m -bit number? Justify your answer.

Short answer

The recursive multiplication algorithm takes$\mathit{O}\mathbf{\left(}{\mathit{m}}^{\mathbf{2}}\mathbf{\right)}$ time.

Step-by-step solution

Recursive algorithms

The recursive function contains a call to itself. The code in recursive function refers to itself while executing the code in the function. The multiplication algorithm is defined as adding the larger number from two numbers for the count equal to the smaller number.

Recursive multiplication function

function$\mathrm{recursive}\mathrm{multiplication}\hspace{0.33em}(\mathrm{a},\mathrm{b})$

Input: Two values i.e.$a,\hspace{0.33em}c$, in which$b\ge 0$

Output: Final product

If $b=0$

Return 0

$\mathrm{c}=\mathrm{recursive}\mathrm{multiplication}(\mathrm{a},\mathrm{b}÷2)$

If b is even:

Return $2\times c$

Else

Return$(a+2)\times c$

Determine time complexity of recursive multiplication algorithm

Refer to recursive multiplication algorithm (page 25) in the textbook. The integer$x$ is$n$ -bit number and$y$is $m$-bit number. The function contains m recursive calls. The value of variable $y$in the multiplication algorithm is halved in each call. The testing of odd and even requires$m$ bit operations. So, with$m$ recursive call and$m$ bit operation in each recursive call, the time complexity of the algorithm is $O\left(m^2\right).$

Therefore, the product of x and y have time complexity of $O\left(m^2\right).$