The maximum gate delay for any output to appear in
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 50 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).