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
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.
3) 4 BIT ADDER
4) 4 AND GATEs REQUIRED B2 MULTIPLY WITH A3 A2 A1 A0.
5) 4 BIT ADDER
6) 4 AND GATEs REQUIRED B3 MULTIPLY WITH A3 A2 A1 A0.
7) 4 BIT ADDER
For 4 bits-->Total Delay= 3+4=7
For n bits--->Total Delay=n-1+n = 2n-1
SO TIME COMPLEXITY WILL BE = ϴ(n)
@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?)
Diagramatic answer seems to helpful. But still dont know how to drive the equation "So the delay is approxiamtely sqrt(2)*(2n-1)."
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 ???
The answer to the first question is $2048 ...