Addition in _2 n+O(1) steps on average. A simple analysis

DOI10.1016/S0304-3975(97)00181-3MaRDI QIDQ1127333zbMATH OpenOpenAlexFDO

Authors Richard Beigel, Bill Gasarch, Ming Li, Louxin Zhang

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)00181-3

zbMATH Keywords

additionaverage case analysisKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• How to Add Fast--on Average
• scientific article; zbMATH DE number 1008511
• Average-case analysis of algorithms using Kolmogorov complexity
• On the number of iterations required by von Neumann addition
• Average-case analysis via incompressibility

Cites work

• How to Add Fast--on Average
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3992805 (Why is no real title available?)
• Some New Results on Average Worst Case Carry

Cited in

(3)

• On the number of iterations required by von Neumann addition
• How to Add Fast--on Average
• Average-case analysis via incompressibility

This page was built for publication: Addition in \(\log_{2} n+O(1)\) steps on average. A simple analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127333)