@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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+30 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

- $\Theta(1)$
- $\Theta(\log n)$
- $\Theta(n)$
- $\Theta(n^2)$

+33 votes

Best answer

Now to MULTIPLY these two Numbers:

- $4$ AND GATEs REQUIRED $B0$ MULTIPLY WITH $A3 \ A2 \ A1 \ A0$.
- $4$ AND GATEs REQUIRED $B1$ MULTIPLY WITH $A3 \ A2 \ A1 \ A0$.
- $4$ BIT ADDER
- $4$ AND GATEs REQUIRED $B2$ MULTIPLY WITH $A3 \ A2 \ A1 \ A0$.
- $4$ BIT ADDER
- $4$ AND GATEs REQUIRED $B3$ MULTIPLY WITH $A3 \ A2 \ A1 \ A0$.
- $4$ BIT ADDER

For $4$ bits, Total Delay$= 3+4=7$

For $n$ bits, Total Delay$=n-1+n = 2n-1$

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

Correct Answer: $C$

+3

0

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 B_{0} with A_{3}A_{2}A_{1}A_{0}, the AND gates used work simultaneously and so the total delay is 1?)

+1

As per the figure, all AND gates can perform their task independently, making all ANDing operation O(1). Only Only adders will face delay of O(n) as last adder will wait for all the above adder to add.

+19 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)

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)

+2

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,763 answers

192,339 comments

90,776 users