GATE CS 2016 Set 1 Q33 — Computer Arithmetic

To find the time complexity of an $n$-bit carry look-ahead adder (CLA) built using gates with a maximum fan-in of 2, we can break down the addition process into three main steps:

1. Generation of Propagate ($p_i$) and Generate ($g_i$) signals:

   For each bit $i$, we compute: $$p_i = a_i \oplus b_i \quad \text{and} \quad g_i = a_i \cdot b_i$$ Since these depend only on the local input bits $a_i$ and $b_i$, they can be computed in parallel in $\Theta(1)$ time using 2-input gates.

2. Carry Computation:

   The carry $C_i$ for each stage is computed using the recurrence relation: $$C_{i} = g_{i-1} + p_{i-1}C_{i-1}$$ Computing all carries is a prefix computation problem. Since the maximum fan-in of the gates is limited to $2$, any circuit combining $n$ variables to compute the carries must have a tree-like structure (such as a Brent-Kung or Kogge-Stone prefix tree).

   The depth of a binary tree with $n$ inputs is $\Theta(\log n)$. Therefore, the time required to propagate and compute all carry signals is $\Theta(\log n)$.

3. Sum Computation:

   Once the carries $C_i$ are available, the sum bits are computed as: $$s_i = p_i \oplus C_i$$ This step takes $\Theta(1)$ time using 2-input XOR gates.

Conclusion:
The total time complexity is dominated by the carry computation step, which is $\Theta(\log n)$.