How To Solve This Using Divide And Conquer
Suppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Divide & conquer method. What is the divide & conquer recurrence, that would arise for the problem.
1. T(n) = 4T(n/2) + O(1)
2. T(n) = 2T(n/2) + O(n)
3. T(n) = 4T(n/2) + O(n^2)
4. T(n) = 4T(n/2) + O(n)