2k 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)$
asked | 2k views
+1
this que is belong to which topic??
0
Combinational Logic

In an $N \times M$ array multiplier we have $N \times M$ AND gates and $(M-1),$ $N-bit$ adders are used.

Total delay in $N \times M (N\geq 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) = (M-1) \times$ delay due to $1$ unit of $N-bit$ adder.  Therefore the maximum gate delay is $O(M)$ but here $M=N \therefore O(N).$

answered by Loyal (7.4k points)
edited
0
Not able to understand the solution :(
Any simple way ?
0
someone explain?
0
what about carry propagating from one adder to next adder

according to this it will take O(n) in one level of computation??
0
Answer is right but need better explanation for this question
0

this may help, in last 10 mins of the video, time complexity is explained!

0
0
great explanation riya mam
maximum Gate delay should be O(2n-1) = O(n)
answered by Veteran (55.6k points)
–1
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

1
2