48 votes 48 votes 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 $\Theta(1)$ $\Theta(\log n)$ $\Theta(n)$ $\Theta(n^2)$ Digital Logic gatecse-2003 digital-logic normal array-multiplier + – Kathleen asked Sep 16, 2014 Kathleen 15.2k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shiva Sagar Rao commented Dec 4, 2020 reply Follow Share Similar question: https://gateoverflow.in/1474/gate1999-1-21 0 votes 0 votes Overflow04 commented Oct 3, 2022 reply Follow Share 5 min will be enough 0 votes 0 votes Please log in or register to add a comment.
Best answer 64 votes 64 votes Thus to MULTIPLY two $4-bit$ numbers the total delay is delay of three $4-bit$ adders plus one AND gate delay. For $n-bits,$ total delay will be delay of $n-bit$ adders (assume ripple-carry as its difficult to do carry propagation beyond $4-bits$) plus one AND gate delay $=\left[2(n-1)+3\right] + 1 = 2(n+1)$ So, Total Delay $=\Theta(n).$ Correct Answer: $C$ VS answered Aug 6, 2017 • edited Dec 16, 2021 by Arjun VS comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments aishwary191 commented Oct 24, 2020 reply Follow Share In the diagram they are using simple adder only (having carry propagated to next bit level sequentially). But then also the adder will take O(1) time instead of O(n) time can be explained by implementation below. We are not propagating carry to the same level rather we are propagating that carry to next level.Which helps us to implement the adder in O(1) by parallely generating the sum as (Ai xor Bi) and carry as (Ai and Bi) for ever i. The implementation is using the fact that when we have to add the three bits and an outstanding carry the result is independent of when we add carry. Example we have to add 5,4 and 3 with carry as 1, then we can add first (5+4+carry) and then add 3 or we can add first (5+4) and then add (9+3+carry) result would be same. 1 votes 1 votes tabish47 commented Feb 6, 2021 reply Follow Share Cant all and gates works in parallel and the effective delay caused by them would be 1 1 votes 1 votes John_Smith commented Dec 11, 2023 reply Follow Share Why is there \(+3\) in \([2(n-1)+3]+1=2(n+1)\) in the best answer (I also made a comment here)? 0 votes 0 votes Please log in or register to add a comment.
25 votes 25 votes Take A = A1 A2 A3 A4 B= B1 B2 B3 B4 NOW TO MULTIPLY THESE TWO NUMBER . 1 AND GATE REQUIRE B1 MULTIPLY WITH A1 A2 A3 A4. 1 AND GATE REQUIRE B2 MULTIPLY WITH A1 A2 A3 A4. 1 AND GATE REQUIRE B3 MULTIPLY WITH A1 A2 A3 A4. 1 AND GATE REQUIRE B4 MULTIPLY WITH A1 A2 A3 A4. NOW 3 OR GATE REQUIRE. TOTAL 7 GATE REQUIRE FOR 4 BIT TAKE N BIT U FIND 2N-1. SO TIME COMPLEXITY WILL BE = ϴ(n) Prashant. answered Nov 22, 2015 Prashant. comment Share Follow See all 2 Comments See all 2 2 Comments reply Prasanna commented Dec 5, 2015 reply Follow Share Diagramatic answer seems to helpful. But still dont know how to drive the equation "So the delay is approxiamtely sqrt(2)*(2n-1)." http://stackoverflow.com/questions/27095216/time-complexity-in-n-bit-array-multiplication 2 votes 2 votes sid1221 commented Dec 12, 2017 reply Follow Share how b1 multply with a1a2a3a4 take only 1 and .. it wil be 4 yes they can perform at same level 1 votes 1 votes Please log in or register to add a comment.
13 votes 13 votes C. $\Theta(n)$ Ref: http://eee.guc.edu.eg/Courses/Electronics/ELCT706%20Microelectronics%20Lab/winter%202014/Multipliers.pdf Arjun answered Mar 10, 2015 Arjun comment Share Follow See all 3 Comments See all 3 3 Comments reply Mithlesh Upadhyay commented May 3, 2015 i reshown by srestha Mar 31, 2016 reply Follow Share if Td = Θ(1) , then the total delay of multiplexer is Θ(n) worst case delay would be (2n+1)td .where td is the time delay of gates. , is it correct ??? 0 votes 0 votes Akash Kanase commented Nov 22, 2015 reply Follow Share Can you give another link of array multiplier ? This link given is not working ! 1 votes 1 votes Dexter commented Nov 20, 2016 reply Follow Share @arjun sir : another link for array multiplier please :( 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes Answer: C The no. of gates used in a n bit array multiplier (n*n) is 2n-1. So, if every single gate takes unit delay, then total delay O(2n-1) = O(n). Rajarshi Sarkar answered Feb 1, 2015 • edited Feb 12, 2015 by Rajarshi Sarkar Rajarshi Sarkar comment Share Follow See all 4 Comments See all 4 4 Comments reply Pradyumna Paralikar asked Mar 8, 2015 Can you please explain how there will be 2n-1 gates will be required ? Himani Srivastava commented Nov 28, 2015 reply Follow Share How number of gates are 2n-1,I am getting n^2 Gates 2 votes 2 votes reboot commented Dec 8, 2020 reply Follow Share I think they mean GATE levels. 0 votes 0 votes Please log in or register to add a comment.