15,061 views
48 votes
48 votes

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)$

4 Answers

Best answer
64 votes
64 votes

 

Thus to MULTIPLY two $4-bit$ numbers the total delay is delay of three $4-bit$ adders plus one AND gate delay.

For $n-bits,$ total delay will be delay of $n-bit$ adders (assume ripple-carry as its difficult to do carry propagation beyond $4-bits$) plus one AND gate delay $=\left[2(n-1)+3\right] + 1 = 2(n+1)$    

So, Total Delay $=\Theta(n).$

Correct Answer: $C$

edited by
25 votes
25 votes
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)
13 votes
13 votes
4 votes
4 votes
Answer: C

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 by
Answer:

Related questions

29 votes
29 votes
3 answers
1
Kathleen asked Sep 23, 2014
11,439 views
The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is$O(n^2)$$O(n)$$O(\log n)$$O(1)$