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.!!
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.