The gate count for addition is at least O(n) though. You should note the O(log n) delay growth is for a logic (ideal) model. Considering the 2D geometry of rea

The gate count for addition is at least O(n) though. You should note the O(log n) delay growth is for a logic (ideal) model. Considering the 2D geometry of real circuits, there are models with more detail, in particular VLSI models. [1] I suspect due to routing and path lengths even the delay would turn out to be O(n) in VLSI, or at least a power of n (with a small constant). [1] Seems like a good introduction: http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter12.pdf http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputa...