### On the complexity of functions for random access machinesOn the complexity of functions for random access machines

Access Restriction
Subscribed

 Author Bshouty, Nader H. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1993 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Greatest common divisor ♦ Indirect addressing ♦ Random access machine ♦ Sorting Abstract Tight bounds are proved for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials, and Rational functions over a $\textit{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 $\textit{finite}$ subdomain. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1993-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 40 Issue Number 2 Page Count 13 Starting Page 211 Ending Page 223

#### Open content in new tab

Source: ACM Digital Library