To be slightly nitpicky, it is problems that belong to complexity classes and not algorithms. Binary search is an algorithm that solves searching in a sorted list.
Funnily, although we usually think of it as having complexity O(log n), that does not hold true for the Turing machine model, with which the complexity classes P and NP are defined.
Comments
To be slightly nitpicky, it is problems that belong to complexity classes and not algorithms. Binary search is an algorithm that solves searching in a sorted list.
Funnily, although we usually think of it as having complexity O(log n), that does not hold true for the Turing machine model, with which the complexity classes P and NP are defined.
Join the rest of us in post-1950's complexity theory. We can use register machines now. Or you can bust out the big bucks and buy a RASP.