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.
