Suppose we are given the η – bit integers, assuming for common sense η 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(η) = 4T(η/2) + C
2
T(η) = 2T(η/2) + η
3
T(η) = 4T(η/2) + η2
4
T(η) = 4T(η/2) + η