Accession Number:

AD0773137

Title:

An Improved Overlap Argument for On-Line Multiplication.

Descriptive Note:

Technical memo.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Report Date:

1974-01-01

Pagination or Media Count:

30.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE