The maximum gate delay for any output to appear in an array multiplier...

The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit numbers is

A. O(n2)
B. O(n)
C. O(logn)
D. O(1)

1Comment
Shamshad Hussain saifi @shamshadhussain
19 Nov 2019 12:39 am

@ Manish Saharan: Take X= X1 X2 X3 X4
                                                   Y   =Y1 Y2 Y3 Y4

Now  to multiply these two number .  
4 AND GATE require Y1 multiply with  X1 X2 X3 X4
4 AND GATE requireY2  multiply with X1 X2 X3 X4

4 Bit Adder
4 AND GATE require Y3 multiply with X1 X2 X3 X4

4 Bit Adder
4 AND GATE require Y4  multiply with  X1 X2 X3 X4

4 Bit Adder

But in ckt  when you see  the internal diagram  4 AND GATE require Y1 multiply with  X1 X2 X3 X4 these 4 AND gates are in parallel 

which is equal to 1 AND gate delay

similarly for Y2 and so on

therefore 

For 4 bits, Total Delay=3+4

For n bits, Total Delay=n−1+n=2n−1

so overall complexity is  = ϴ(n)

Pages