arXiv
Open Access
2023
A note on the complexity of addition
Emil Jeřábek
Abstrak
We show that the sum of a sequence of integers can be computed in linear time on a Turing machine. In particular, the most obvious algorithm for this problem, which appears to require quadratic time due to carry propagation, actually runs in linear time by amortized analysis.
Topik & Kata Kunci
Penulis (1)
E
Emil Jeřábek
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2023
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓