Suppose you design an algorithm to multiply two n-bit integers x and y. The general multiplication technique takes T (n) = O (n2) time. For a more efficient algorithm, you first split each of x and y into their left and right halves, which are n=2 bits long. For example, if x = 100011012, then xL = 10002 and xR = 11012, and x = 24 xL + xR. Then the product of x and y can be re-written as the following: x y = 2n (xL yL) + 2n=2 (xL yR + xR yL) + (xR yR)

See Explaination

Explanation:

a) Assume there are n nits each in x and y. SO we divide them into n/2 and n/2 bits.

x = xL * 2^{n/2} + xR

y = yL * 2^{n/2} + yR

x. y = 2^{n}. (xL. yL) + 2^{n/2}. (xL. yR + xR. yL) + (xR. yR)

If you see there are 4 multiplications of size n/2 and we took all other additions and subtractions as O (n).

So T (n) = 4*T (n/2) + O (n)

Now lets find run time using master theorem.

T (n) = a * T (n/b) + O (n^{d})

a = 4

b = 2

d = 1

if a > b^{d}

T (n) = O (n^v) where v is log a base b

In our case T (n) = O (n^v) v = 2

=> T (n) = O (n^{2})

The splittinng method is not benefecial if we solve by this way as the run time is same even if go by the naive approach

b)

x. y = 2^{n}. (xL. yL) + 2^{n/2}. ((xL+xR). (yL+yR) - (xL. yL) - (xR. yR)) + (xR. yR)

Here we are doing only three multipliactions as we changed the term.

So T (n) = 3*T (n/2) + O (n)

a = 3

b = 2

d = 1

if a > b^{d}

T (n) = O (n^v) where v is log a base b

In our case T (n) = O (n^v) v = log 3 base 2

v = 1.584

So T (n) = O (n^{1.584})

As we can see this is better than O (n^{2}). Therefore this algorithm is better than the naive approach.