How is the time complexity of carry look ahead adder O(log n)? Can you explain in terms of gate delays?
\$\begingroup\$
\$\endgroup\$
5
-
2\$\begingroup\$ Possible duplicate of How to find gate delay for 4-bit look-ahead carry adder? \$\endgroup\$– RoyCCommented Mar 30, 2017 at 8:05
-
1\$\begingroup\$ @RoyC the question or answer don't involve how to calculate gate delays, I don't think it is the same \$\endgroup\$– Voltage Spike ♦Commented Mar 30, 2017 at 15:13
-
1\$\begingroup\$ @RoyC In that answer, the time complexity is O(1), as the carry is always produced after 3 gate delays irrespective of the no of bits. I came across many places where it is mentioned that the time complexity of carry look ahead adder is log n. So, I don't understand why it is O(log n) and not O(1). So this question is not a duplicate and is new one. \$\endgroup\$– ArteezyCommented Mar 31, 2017 at 20:09
-
\$\begingroup\$ I am sure these PowerPoint slides (from slide #30) will answer your doubt. \$\endgroup\$– Sahil SinghCommented Sep 24, 2019 at 0:17
-
\$\begingroup\$ @SahilSingh Wow, that's exactly what I needed. It perfectly explains to my satisfaction. Thanks but it's 2.5 years late. Wish I had found this while learning it haha \$\endgroup\$– ArteezyCommented Sep 25, 2019 at 1:32
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
We could think of a carry look-ahead adder as made up of two "parts"
- The part that computes the carry for each bit
- The part that adds the input bits and the carry for each bit position
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
