GATE 2003
March 19, 2025GATE 2003
March 19, 2025GATE 2003
|
Question 11
|
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
|
Θ (1)
|
|
|
Θ (log n)
|
|
|
Θ (n)
|
|
|
Θ (n2)
|
Question 11 Explanation:
Each bit in Multiplier is ANDed with a bit in Multiplicand which produce n n-bit numbers. The multiplication takes n units of time. The n n-bit numbers are added by using (n-1) n-bit adders. The time taken by (n-1) n-bit adders is k*(n-1) units.
The total time is n+kn-k = Θ(n)
The total time is n+kn-k = Θ(n)
Correct Answer: C
Question 11 Explanation:
Each bit in Multiplier is ANDed with a bit in Multiplicand which produce n n-bit numbers. The multiplication takes n units of time. The n n-bit numbers are added by using (n-1) n-bit adders. The time taken by (n-1) n-bit adders is k*(n-1) units.
The total time is n+kn-k = Θ(n)
The total time is n+kn-k = Θ(n)