ON THE COMPLEXITY OF FUNCTIONS FOR RANDOM-ACCESS MACHINES

Tight bounds are proved for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials, and Rational functions over a finite inputs domain, in a random access machine with arithmetic operations, direct and indirect addressing, unlimited power for answering YES/NO questions, branching, and tables with bounded size. These bounds are also true even if additions, subtractions, multiplications, and divisions of elements by elements of the field are not counted. In a random access machine with finitely many constants and a bounded number of types of instructions, it is proved that the complexity of a function over a countable infinite domain is equal to the complexity of the function in a sufficiently large finite subdomain.