Is it safe to say a ripple-carry adder has O(n) and the look-ahead carry adder has O(1)?
A Question for Electrical and Computer Engineers
While it's marginally safe to say that a ripple-carry adder has O(n) complexity, I don't think you can say that a carry-lookahead adder has O(1). As you increase n, the number of gates you require increases tremendously (by a factor of O(n^2), actually) as well as (more importantly) the number of inputs to your gates (especially the OR gates), which ends up making them much slower.
I'm not sure what the performance analysis would be off the top of my head, but it's surely more than constant time.
I'm not sure what the performance analysis would be off the top of my head, but it's surely more than constant time.
 |