0
$\begingroup$

Basic Approach to multiply 2 numbers say x , y $\left(binary\right)$ is $\Theta \left ( n^{2} \right )$ but if we apply Divide and conquer approach , we split it as-:

$x=x_{L}*2^{n/2}+x_{R}$

$y=y_{L}*2^{n/2}+y_{R}$

$x_{L}$ and $x_{R}$ contains leftmost and rightmost $n/2$ bits of $x$ respct. and same for $y_{L}$ and $y_{R}$

$x*y=2^{n}*x_{L}*y_{L}+2^{n/2}*\left (\left ( x_{L}*y_{R} \right )+ \left ( x_{R}*y_{L} \right )\right )+x_{R}*y{R}$

From the equation ,it is clear that we require 4 recursive calls to multiply 4 terms.

The recursive equation is given as-:

$f\left ( n \right )=4*f\left ( n/2 \right )+\Theta \left ( n \right )$

what is this $\Theta \left(n\right)$???? isn't it $\Theta \left(n^{2}\right)$ because it requires $\Theta \left(n^{2}\right)$ for simple multiplication..please help me out.!!

$\endgroup$
1
$\begingroup$

There are no simple multiplications in the RHS $2^{n}*x_{L}*y_{L}+2^{n/2}*\left (\left ( x_{L}*y_{R} \right )+ \left ( x_{R}*y_{L} \right )\right )+x_{R}*y_{R}$. As you've already noted there are four recursive multiplications: $x_{L}*y_{L}, x_{L}*y_{R}, x_{R}*y_{L}, x_{R}*y_{R}$. The only remaining multiplications are by powers of $2$, which just requires shifting an array of digits by a fixed offset: this only takes $\Theta(n)$ operations provided the array length is $\Theta(n)$ and the offset is $O(n)$. Besides multiplications, the only thing left are additions, which are again $\Theta(n)$.

Of course, solving this recurrence still gives $\Theta(n^2)$. The key to Karatsuba's algorithm for doing this more efficiently is a trick that lets you compute all four recursive multiplications using only three distinct multiplications.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you please provide a brief algo or link of "shifting an array and then addition " @Erick $\endgroup$ – virat Nov 1 '16 at 7:24
  • $\begingroup$ @sourav It's no different from multiplying a decimal number by $10000000$. These numbers are stored in binary — just think about it. $\endgroup$ – Erick Wong Nov 1 '16 at 7:41

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.