Technical Report CS0583

Title: Lower Bounds For the Complexity of Functions in Random Access Machines
Authors: Nader H. Bshouty
Abstract: We prove tight bounds for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials and Rational functions with finite inputs domain in random access machine with arithmetic operations, direct and indirect addressing, unlimited power of answering YES/NO questions, branching and tables with bounded size. These bounds are also true even if we do not count additions, subtractions, multiplication and division by elements of the field. In random access machine with finite initial constants and bounded types of instructions we prove that the complexity of a function in infinite countable domain is equal to the complexity of the function in sufficient large finite subdomain.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion