1

How is the time complexity of carry look ahead adder O(log n)? Can you explain in terms of gate delays?

Arteezy
  • 35
  • 1
  • 4
  • 2
    Possible duplicate of [How to find gate delay for 4-bit look-ahead carry adder?](http://electronics.stackexchange.com/questions/156852/how-to-find-gate-delay-for-4-bit-look-ahead-carry-adder) – RoyC Mar 30 '17 at 08:05
  • 1
    @RoyC the question or answer don't involve how to calculate gate delays, I don't think it is the same – Voltage Spike Mar 30 '17 at 15:13
  • 1
    @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. – Arteezy Mar 31 '17 at 20:09
  • I am sure [these PowerPoint slides](http://www.cse.iitd.ernet.in/~srsarangi/files/bookppts/Chapter_07_Computer_Arithmetic_1.pptx) (from slide #30) will answer your doubt. – Sahil Singh Sep 24 '19 at 00:17
  • @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 – Arteezy Sep 25 '19 at 01:32

1 Answers1

2

We could think of a carry look-ahead adder as made up of two "parts"

  1. The part that computes the carry for each bit
  2. 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

j3h
  • 103
  • 2
Vaibhav
  • 36
  • 3