The Gateway to Computer Science Excellence

0 votes

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)+n^{2}

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

0 votes

0 votes

A=(a_{n,}a_{n-1,}a_{n-2................}a_{0})_{2} and B=(b_{n},b_{n-1},.....................b_{0}) be 2 n bit no

then A can be written as A=2^n/2A_{msb+}A_{lsb }

B=2^n/2B_{msb+B}_{lsb }

_{ }A_{msb }is the n/2 most significant bit of A ie n/2 leftmost bit of the no.

A_{lsb }is the n/2 least significant bit of A ie is n/2 rightmost bit of the no.

so A*B=(2^n/2A_{msb + }A_{lsb })( 2^n/2B_{msb + B}_{lsb }) = 2^n*A_{msb*}B_{msb + }2^n/2(A_{msb }*_{ B}_{lsb } +_{ }A_{lsb }*B_{msb}) + _{ }A_{lsb }_{ B}_{lsb }

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,241 answers

198,008 comments

104,601 users