The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
200 views

suppose you are given n bit integers asuming for common sense n as power of 2 .it is required to multiply them using divide and conquer method .what is the divide and conquer recurrence that would arise for the problem

a) T(n)=4T(n/2)+c      

b) a) T(n)=2T(n/2)+n              

c) a) T(n)=4T(n/2)+n2          

d) a) T(n)=4T(n)+n

asked in Algorithms by Active (3.3k points) | 200 views

2 Answers

0 votes
According to Gauss method answer should be T(n) = T(n/2) + n

Otherwise T(n) = 4T(n/2) + n
answered by Veteran (55.6k points)
0
why you are dividing problem in to 4 parts.can you please explain a bit more
0 votes

A=(an,an-1,an-2................a0)2  and B=(bn,bn-1,.....................b0)  be 2 n bit no

then A can be written as A=2^n/2Amsb+Alsb  

                                    B=2^n/2Bmsb+Blsb

 Amsb is the n/2 most significant bit of A ie n/2 leftmost bit of the no.

Alsb   is the n/2  least significant bit of A ie is n/2 rightmost bit of the no.

so A*B=(2^n/2Amsb    +      Alsb  )(   2^n/2Bmsb     +    Blsb )   =   2^n*Amsb*Bmsb  +    2^n/2(Amsb * Blsb   + Alsb *Bmsb)  +    Alsb    Blsb 

this equation says that mul of 2 n bit no can be carried out using mul of 4 n/2 digit no +some shift operatin 

so the required corresponding recurrence if T(n)= time complexity to mul 2 n bit no

T(n)  =  4*T(n/2)   +Cn

but it can also be solved in T(n)=  3*T(n/2) +cn

for more optimiation ---https://en.wikipedia.org/wiki/Karatsuba_algorithm

answered by Active (2.3k points)

Related questions

0 votes
1 answer
2


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,312 questions
49,803 answers
164,513 comments
65,865 users