How is the time complexity of carry look ahead adder O(log n)? Can you explain in terms of gate delays?
Electronic – Time complexity of carry look ahead adder
addercarry-look-ahead
Related Topic
- Electronic – How to determine if a Carry Look Ahead Adder Overflows
- Electronic – Carry-lookahead adder – what happens to carry bit
- Carry Look ahead adder Propagate & Generate Outputs
- Electronic – How to calculate Gate Delays in normal Adders and Carry Look Ahead Adders
- Electronic – How to find gate delay for 4-bit look-ahead carry adder
- Carry look ahead adder with 2-input gates
Best Answer
We could think of a carry look-ahead adder as made up of two "parts"
The \$log(n)\$ complexity arises from the part that generates the carry, not the circuit that adds the bits.
Now, for the generation of the \$n^{th}\$ carry bit, we need to perform a AND between (n+1) inputs (if why this is so is a doubt, you may see this link)
The complexity of the adder comes down to how we perform this AND operation. If we have AND gates, each with a fan-in (number of inputs accepted) of \$k\$, then we can find the AND of all the bits in \$(log_{k}(n+1))\$ time. This is represented in asymptotic notation as \$ \Theta (log \ n)\$.
Hope that helps