Divide and conquer

Question

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)

Answer 1

https://gateoverflow.in/16209/what-the-divide-conquer-recurrence-that-would-arise-problem

 

chk this