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)
- Θ(logn)
- Θ(n)
- Θ(n^2)
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 ?
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)