Time complexity in n bit array multiplication

2.6k views Asked by At

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

There are 2 answers

0
Bhushan On BEST ANSWER

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)

1
Pavan Kumar On

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