Addition in log2n + O(1) steps on average a simple analysis
Richard Beigel, Bill Gasarch, Ming Li, Louxin Zhang · Theoretical Computer Science · 1998
We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log2 n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).