Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

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.