Addition in log2 n + 0(1) steps on average A simple analysis

Richard Beigel; Bill Gasarch; Ming Li; Louxin Zhang

doi:10.1016/S0304-3975(97)00181-3

Addition in log₂ n + 0(1) steps on average A simple analysis

Richard Beigel, Bill Gasarch, Ming Li, Louxin Zhang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log₂ n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).

Original language	English
Pages (from-to)	245-248
Journal	Theoretical Computer Science
Volume	191
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(97)00181-3
Publication status	Published - 30 Jan 1998
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href="mailto:[email protected]">[email protected]</a>.

Funding

Supported in part by NSF grants CCR-8952528, CCR-9415410, and CCR-9522084 and by NASA (NAG52895).

Research Keywords

Addition
Average case analysis
Kolmogorov complexity

Access Output

10.1016/S0304-3975(97)00181-3

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{943a5304c2754b0e8946217bbec654ca,

title = "Addition in log2 n + 0(1) steps on average A simple analysis",

abstract = "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).",

keywords = "Addition, Average case analysis, Kolmogorov complexity",

author = "Richard Beigel and Bill Gasarch and Ming Li and Louxin Zhang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href={"}mailto:[email protected]{"}>[email protected]</a>.",

year = "1998",

month = jan,

day = "30",

doi = "10.1016/S0304-3975(97)00181-3",

language = "English",

volume = "191",

pages = "245--248",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Addition in log2 n + 0(1) steps on average A simple analysis

AU - Beigel, Richard

AU - Gasarch, Bill

AU - Li, Ming

AU - Zhang, Louxin

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href="mailto:[email protected]">[email protected]</a>.

PY - 1998/1/30

Y1 - 1998/1/30

N2 - 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).

AB - 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).

KW - Addition

KW - Average case analysis

KW - Kolmogorov complexity

UR - http://www.scopus.com/inward/record.url?scp=0345757832&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0345757832&origin=recordpage

U2 - 10.1016/S0304-3975(97)00181-3

DO - 10.1016/S0304-3975(97)00181-3

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 191

SP - 245

EP - 248

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -