An Improved Overlap Argument for On-Line Multiplication.
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Pagination or Media Count:
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 cNlogNloglogN. These bounds compare favorably with known upper bounds of the form cNlogNk 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
- Theoretical Mathematics