ADDITION IN LOG(2) N- A SIMPLE ANALYSIS(O(1) STEPS ON AVERAGE )

Authors
BEIGEL R GASARCH B LI M ZHANG LX
Citation
R. Beigel et al., ADDITION IN LOG(2) N- A SIMPLE ANALYSIS(O(1) STEPS ON AVERAGE ), Theoretical computer science, 191(1-2), 1998, pp. 245-248
Citations number
7
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
191
Issue
1-2
Year of publication
1998
Pages
245 - 248
Database
ISI
SICI code
0304-3975(1998)191:1-2<245:AILNAS>2.0.ZU;2-Z
Abstract
We demonstrate the use of Kolmogorov complexity in average case analys is of algorithms through a classical example: adding two n-bit numbers in [log(2)n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (19 95).