Jay Teli
Jay Teli

Reputation: 1022

Time complexity in n bit array multiplication

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. Θ(1)
  2. Θ(logn)
  3. Θ(n)
  4. Θ(n^2)

Upvotes: 1

Views: 2791

Answers (2)

Bhushan
Bhushan

Reputation: 364

Multiplication of unsigned numbers using array of full adders

If you see the image above you will notice that delay caused is diagonal to the array.
So the delay is approxiamtely sqrt(2)*(2n-1).
Which is Θ(n)

Upvotes: 1

Pavan Kumar
Pavan Kumar

Reputation: 1

The no. of gates used in n bit array multiplier(nxn) is 2n-1. So. if every single gate takes unit delay, then total delay 0(2n-1)=0(n) It is of linear order

Upvotes: 0

Related Questions