2.5k views

Consider an array multiplier for multiplying two $n$ bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

1. $\Theta(1)$
2. $\Theta(\log n)$
3. $\Theta(n)$
4. $\Theta(n^2)$

NOW TO MULTIPLY THESE TWO NUMBERs:

1 ) 4 AND GATEs REQUIRED B0 MULTIPLY WITH A3 A2 A1 A0.

2 ) 4 AND GATEs REQUIRED B1 MULTIPLY WITH A3 A2 A1 A0.

4) 4 AND GATEs REQUIRED B2 MULTIPLY WITH A3 A2 A1 A0.

6) 4 AND GATEs REQUIRED B3 MULTIPLY WITH A3 A2 A1 A0.

For 4 bits-->Total Delay= 3+4=7

For n bits--->Total Delay=n-1+n = 2n-1

SO TIME COMPLEXITY WILL BE = ϴ(n)

selected

@VS ji. Thanks for valuable effort. Just small addition if look ahead carry adder is used then 4-Unit of delay in each adder. But it will  not change answer because 4 is  a constant with respect to n.

16 AND gates are used, but in the calculation 4 are considered...is it because every time 4 AND gates will work simultaneously? (Like for multiplication of B0 with A3A2A1A0, the AND gates used work simultaneously and so the total delay is 1?)

Take A = A1 A2 A3 A4

B=   B1 B2 B3 B4

NOW TO MULTIPLY THESE TWO NUMBER .

1 AND GATE REQUIRE B1 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B2 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B3 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B4 MULTIPLY WITH A1 A2 A3 A4.

NOW 3 OR GATE REQUIRE.

TOTAL 7 GATE REQUIRE FOR 4 BIT TAKE N BIT U FIND 2N-1.

SO TIME COMPLEXITY WILL BE = ϴ(n)

Diagramatic answer seems to helpful. But still dont know how to drive the equation "So the delay is approxiamtely sqrt(2)*(2n-1)."

http://stackoverflow.com/questions/27095216/time-complexity-in-n-bit-array-multiplication

how b1 multply with a1a2a3a4 take only 1 and .. it wil be 4 yes they can perform at same level

if Td = Θ(1) , then the total delay of multiplexer is Θ(n)
worst case delay would be
(2n+1)td .where td is the time delay of gates. , is it correct ???

Can you give another link of array multiplier ? This link given is not working !

The no. of gates used in a n bit array multiplier (n*n) is 2n-1.

So, if every single gate takes unit delay, then total delay O(2n-1) = O(n).
edited
How number of gates are 2n-1,I am getting n^2 Gates