Thumbnail
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

   Open content in new tab
Source: ACM Digital Library