retagged by
459 views
1 votes
1 votes

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)

retagged by

1 Answer

Related questions

1 votes
1 votes
2 answers
3
manvi_agarwal asked Sep 3, 2018
648 views
https://gateoverflow.in/?qa=blob&qa_blobid=11583750777176064728Approach please
0 votes
0 votes
0 answers
4
iarnav asked Jan 12, 2018
548 views
in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1) How to reach...