Consider an array multiplier for multiplying two n bit numbers. If each gate…

Answer: Θ(n).

Key idea: The critical path in a simple array multiplier involves generating partial products and then adding them with carry propagation across bit positions. The carry can ripple through O(n) adder stages, giving linear delay.

• Partial-product generation: Each partial product is produced by an AND gate (one gate delay).

• Addition of partial products: The array arranges adders so that carries can propagate from the least-significant column to the most-significant column. Each full adder contributes constant gate delay.

• Critical path: A signal may need to go through one partial-product AND plus up to O(n) adder-stage carry propagations, so the total delay is proportional to n.

Note: Achieving sublinear delay (for example Θ(log n)) requires using faster adder structures (like carry-lookahead or tree adders) inside the multiplier. The standard array multiplier, however, uses ripple-style addition and therefore has Θ(n) delay.