The GATE Grind

GATE 2016 CS – Question 43

Computer Organization and Architecture · ALU and Control Unit Design · 2 marks · Multiple choice

Consider a carry lookahead adder for adding two $n$-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

  1. $\Theta(1)$
  2. $\Theta(\log(n))$
  3. $\Theta(\sqrt{n})$
  4. $\Theta(n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(\log(n))$

Explanation

A carry lookahead adder computes every carry from the generate and propagate signals with a tree of gates. With gates of fan-in two, combining $n$ signals takes a tree of depth $\log n$, so the addition time is $\Theta(\log n)$.