A model in which an algorithm learns the relative order or equality of input keys by comparisons. Lower-bound reductions must preserve the information available to each comparison; transforming numbers and allowing stronger tests without justification can change the model. For intervals built from integers, every endpoint comparison can be simulated by comparing original keys and then fixed offsets.
A single comparison returning one of three outcomes: less than, equal to, or greater than. A comparison model may count this as one operation even when a programming language expresses the outcomes using multiple Boolean tests. Binary search on ordered keys uses one such comparison per inspected position.
Articles by others on the same topic
There are currently no matching articles.