Home > Binary search
4 Applications to complexity theoryComplexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it
Even if we don't know a fixed range the number k falls in, we can still determine its value by asking simple yes/no questions of the form "Is k greater than x?" for some number x. As a simple consequence of this, if you can answer the question "Is this integer property k greater than a given value?" in some amount of time then you can find the value of that property in the same amount of time with an added factor of log k. This is called a reductionIn computational complexity theory, a reduction is a class of techniques used to solve a problem using the solution of another problem. Roughly speaking, if a problem A reduces to a problem B, this means A is no harder than B, and B is no easier A. We wri, and it is because of this kind of reduction that most complexity theorists concentrate on decision problemIn logic a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. a true or false or yes or no . These are also known as yes-or-no questions. For example, thes, algorithms that produce a simple yes/no answer.
For example, suppose we could answer "Does this n x n matrix have determinant larger than k?" in O(n2) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n2log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output.
