DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD0773137
Title:
An Improved Overlap Argument for On-Line Multiplication.
Corporate Author:
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Report Date:
1974-01-01
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 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
Descriptive Note:
Technical memo.,
Pages:
0030
Contract Number:
N00014-70-A-0362-0003
Contract Number 2:
NSF-GJ-34671
File Size:
0.00MB
