142 views

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)

by