Reputation: 1022
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 ?
Upvotes: 1
Views: 2791
Reputation: 364
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
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