The maximum gate delay for any output to appear in an array multiplier for…
1999
The maximum gate delay for any output to appear in an array multiplier for multiplying two n-bit numbers is:
- A.
O(n²)
- B.
O(n)
- C.
O(log n)
- D.
O(1)
Attempted by 37 students.
Show answer & explanation
Correct answer: B
The correct answer is: O(n).
In a standard combinational array multiplier, all partial products are generated in parallel using AND gates. These partial products are then added through a regular array of adders.
The longest signal path does not pass through all n² adders. Instead, the critical path passes through a linear number of adder/carry stages, typically along a diagonal path through the array.
Thus the maximum gate delay grows proportional to n, not n².
So the maximum delay is O(n).