Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-051 | 1st October 1996 00:00

Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

RSS-Feed




TR96-051
Authors: Richard Beigel, William Gasarch, Ming Li, Louxin Zhang
Publication: 2nd October 1996 09:27
Downloads: 1305
Keywords: 


Abstract:

We demonstrate the use of Kolmogorov complexity in average case
analysis of algorithms through a classical example: adding two $n$-bit
numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the
analysis of Burks, Goldstine, and von Neumann in 1946 and
(in more complete forms) of Briley and of Schay.



ISSN 1433-8092 | Imprint