The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

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 in Digital Logic by Veteran (59.6k points) | 1.9k views
this que is belong to which topic??
Combinational Logic

2 Answers

+14 votes
Best answer

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).$

Refer this article page 16.

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

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

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


+3 votes
maximum Gate delay should be O(2n-1) = O(n)
answered by Veteran (55.4k points)
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

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,871 questions
47,532 answers
62,298 users