An Improved Overlap Argument for On-Line Multiplication.
Abstract
A lower bound of cNlogN is proved for the mean time complexity of an on-line multitape. Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines which includes some models of random-access machines, the corresponding bound is cNlogN/loglogN. These bounds compare favorably with known upper bounds of the form cN(logN)k sub K, and for some classes the upper and lower bounds coincide. The proofs are based on the 'overlap' argument due to Cook and Aanderaa. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1974
- Accession Number
- AD0773137
Entities
People
- Albert R. Meyer
- Michael J. Fischer
- Michael S. Paterson
Organizations
- Massachusetts Institute of Technology