1.6k views

The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is

1. $O(n^2)$
2. $O(n)$
3. $O(\log n)$
4. $O(1)$
+1
this que is belong to which topic??

In a N X M array multiplier we have N * M AND gates and (M-1), N bit adders used.

Total delay in N X M (N>=M) array multiplier due to AND gate in partial products at all level is just 1 unit AND gate delay as the operation is done parallel wise at each step. Now delays at level 1 to (M-1) is = (M-1)*delay due to 1 unit of N bit adder.  Therefore the maximum gate delay is O(M) but here M=N therefore O(N).

edited
0
Not able to understand the solution :(
Any simple way ?
0
someone explain?
0

according to this it will take O(n) in one level of computation??
0
Answer is right but need better explanation for this question
maximum Gate delay should be O(2n-1) = O(n)
0
I think O(n2) 2n gate delay at each n-1 bit parallel adder level There'll be n-1 such levels Extra 1 and gate level So total 2n*(n-1) +1
0
@Digvijay

can you please elaborate the explanation ?
0
2n-1 ?? how ??
+1