@kshitij provided an excellent NPTEL video below to understand array multipliers – https://youtu.be/5-PI4T25OXI
Based on what I understand from the video, your adders do not need to be carry look ahead adders. Yes, carry look ahead adders do speed up the process, but the speed up does not affect the asymptotic time complexity of the array multiplier circuit (which is what the question asks for), assuming the time taken to generate a sum or a carry by a single full adder/half adder circuit (inside a carry look ahead adder, or a ripple carry adders, or any such multi-bit adder circuit) to be \(O(1)\). You can very well use ripple carry adders in your array multiplier circuit, due to which its asymptotic time complexity equals the time for the last adder to generate the last carry bit to be placed in the product (i.e., \(P_{n+m-1}\), if we were to denote the product as \(P_{n+m-1} \ P_{n+m-2}\ ...\ P_0\); note that the size of the product is equal to the sum of the sizes of the multiplicand and the multiplier), because all the other operations in the array multiplier circuit is taking place simultaneously as the carry is getting propagated. And, the time for that carry to propagate is nothing but \(O(1)\) (to form the first partial product, and to produce the first carry from \(a_0b_1+a_1b_0\)) \(\ + \ \) \(O\big((n-1)+(m-1)\big)\) (since the carry traverses \((n-1)\) bits in the first adder, then falls off as one the last input bits in the second adder, falls off as one the last input bits in the third adder,…,one the last input bits in the \((m-1)\)th adder, and falls of into \(P_{n+m-1}\); it similar to going from \((1,1)\) to \((n-1,m-1)\) in a \((n-1)\times (m-1)\) sized grid, via \((n-1)\) left/right moves, followed by \((m-1)\) up/down moves) \(=O(n+m)\). So the asymptotic time complexity of the array multiplier circuit using any form of multi-bit adders is \(O(n+m)\). As \(n=m\) in the above question, we have the asymptotic time complexity of the array multiplier circuit as \(O(n+n)=O(n)\).
P.S. Why isn’t using carry look ahead adder reducing the asymptotic time complexity of the array multiplier circuit? It’s because we forget that the (complex) carry generation circuitry of any \((i+1)\)th level adder cannot proceed unless the output from the \(i\)th level adder is available, so a similar logic as above works in this case as well.
