Context of computational complexity
Encyclopedia
In computational complexity theory
and analysis of algorithms
, a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem. Interpreting these metrics meaningfully requires context, and this context is frequently implicit and depends on the field and the problem under consideration. This article describes a number of important pieces of context and how they affect metrics.
requires O(n2) comparisons is meaningless without defining n, which in this case is the number of elements in the input list.
Because many different contexts use the same letters for their variables, confusion can arise. For example, the complexity of primality test
s and multiplication algorithm
s can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of binary
digits (bits) in those integers. For example, if n is the integer being tested for primality, trial division
can test it in Θ(n1/2) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2n/2) time. In the fields of cryptography
and computational number theory
, it is more typical to define the variable as the number of bits in the input integers.
In the field of computational complexity theory
, the input is usually specified as a binary string (or a string in some fixed alphabet), and the variable is usually the number of bits in this string. This measure depends on the specific encoding of the input, which must be specified. For example, if the input is an integer specified using unary coding
, trial division will require only Θ(n1/2) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to Θ(2n/2) operations, not because the algorithm is taking any additional time, but because the number of bits in the input n has become exponentially smaller. In the other direction, succinct circuits are compact representations of a limited class of graph
s that occupy exponentially less space than ordinary representations like adjacency lists. Many graph algorithms on succinct circuits are EXPTIME-complete, whereas the same problems expressed with conventional representations are only P-complete
, because the succinct circuit inputs have smaller encodings.
Output-sensitive algorithm
s define their complexity not only in terms of their input but also their output. For example, Chan's algorithm
can compute the convex hull
of a set of points in O(n log h) time, where n is the number of points in the input and h is the number of points in the resulting convex hull, a subset of the input points. Because every input point might be in the convex hull, an analysis in terms of the input alone would yield the less precise O(n log n) time.
The complexity of some algorithms depends not only on parameters of the input but also parameters of the machine the algorithm is being run on; as mentioned in #Metric being measured below, this is typical in analyzing algorithms that run on systems with fixed cache hierarchies, where the complexity may depend on parameters such as cache size and block size.
. For example, on a random access machine
, binary search
can be used to rapidly locate a particular value in a sorted list in only O(log n) comparisons, where n is the number of elements in the list; on a Turing machine
, this is not possible, since it can only move one memory cell at a time and so requires Ω(n) steps to even reach an arbitrary value in the list.
Moreover, different abstract machines define different primitive operations, which are operations that can be performed in constant time. Some machines, like Turing machines, only permit one bit at a time to be read or written; these are called bit operations, and the number of bit operations required to solve a problem is called its bit complexity. Bit complexity generalizes to any machine where the memory cells are of a fixed size that does not depend on the input; for this reason, algorithms that manipulate numbers much larger than the registers on ordinary PCs are typically analyzed in terms of their bit complexity. Put another way, the bit complexity is the complexity when the word size is a single bit, where word size is the size of each memory cell and register.
Another commonly-used model has words with log n bits, where n is a variable depending on the input. For example, in graph algorithms, it is typical to assume that the vertices are numbered 1 through n and that each memory cell can hold any of these values, so that they can refer to any vertex. This is justified in problems where the input uses Ω(n) words of storage, since on real computers, the memory cell and register size is typically selected in order to be able to index any word in memory. Operations on these words, such as copies and arithmetic operations, are assumed to operate in constant time, rather than O(log n) time. The number of word operations required to solve a problem in this model is sometimes called its word complexity.
In computational complexity theory
, researchers intentionally define complexity class
es in a way intended to make them machine-independent - that is, if a problem lies in a particular class relative to a particular "reasonable" machine, it will lie in that class relative to any "reasonable" machine. For example, as mentioned above, the time complexity of binary search
depends on whether a Turing machine or a random access machine is used; but regardless of the machine choice, it lies in P
, the class of polynomial-time algorithms. In general, P is considered a machine-independent class because any operation that can be simulated in polynomial time can be assumed to require constant time, since it can be treated as a subroutine without exceeding the polynomial-time bound.
Oracle machine
s are machines that have a specific operation that they can perform in constant time; this operation can be arbitrarily complex and can dramatically affect the complexity of algorithms performed on the machine. For example, if one has an oracle to solve any NP-complete
problem, then any problem in NP
can be solved in polynomial time (whereas without the oracle, no polynomial-time algorithm is known for many of these problems). Oracle machines are impractical to construct but useful in theory for determining which proof techniques will be effective.
requires O(n2) time; however, it doesn't make sense to say that the bit complexity of insertion sort is O(n2), unless the elements being sorted are of constant size. If the elements are assumed to be integers between 1 and n, then the word complexity where words have log n bits would be O(n2), but it's preferable to have a model that allows sorting of lists other than lists of small integers, such as lists of strings. In this case, instead of measuring the number of time steps the abstract machine takes, it's preferable to define a particular metric appropriate to the problem at hand. For comparison sort
algorithms, which examine the input using only comparisons and modify it using only exchanges (swaps), the typical metric is either the number of element comparisons performed, the number of element exchanges performed, or the sum of these. Different comparison sort algorithms can be compared using these metrics, but for useful comparison with non-comparison sorting algorithms, such as radix sort
, a different metric must be used, and the set of elements must be restricted.
Because disk operations are orders of magnitude slower than accesses to main memory, the typical metric used in disk-based algorithms is the number of disk seeks or the number of blocks read from the disk, which depend on both the input and the parameters of the disk. RAM accesses and CPU operations are "free." Similarly, in many models used to study data structures, such as the cache-oblivious model, operations on cached data are considered "free" because they are typically orders of magnitude faster in practice than access to main memory. Consequently, the typical metric used is the number of cache misses, which depends on both the input and parameters of the cache.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
, a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem. Interpreting these metrics meaningfully requires context, and this context is frequently implicit and depends on the field and the problem under consideration. This article describes a number of important pieces of context and how they affect metrics.
Definitions of variables
Metrics are usually described in terms of variables that are a function of the input. For example, the statement that insertion sortInsertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
requires O(n2) comparisons is meaningless without defining n, which in this case is the number of elements in the input list.
Because many different contexts use the same letters for their variables, confusion can arise. For example, the complexity of primality test
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
s and multiplication algorithm
Multiplication algorithm
A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
s can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
digits (bits) in those integers. For example, if n is the integer being tested for primality, trial division
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
can test it in Θ(n1/2) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2n/2) time. In the fields of cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and computational number theory
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
, it is more typical to define the variable as the number of bits in the input integers.
In the field of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the input is usually specified as a binary string (or a string in some fixed alphabet), and the variable is usually the number of bits in this string. This measure depends on the specific encoding of the input, which must be specified. For example, if the input is an integer specified using unary coding
Unary coding
Unary coding, sometimes called thermometer code, is an entropy encoding that represents a natural number, n, with n ones followed by a zero or with n − 1 ones followed by a zero...
, trial division will require only Θ(n1/2) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to Θ(2n/2) operations, not because the algorithm is taking any additional time, but because the number of bits in the input n has become exponentially smaller. In the other direction, succinct circuits are compact representations of a limited class of graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
s that occupy exponentially less space than ordinary representations like adjacency lists. Many graph algorithms on succinct circuits are EXPTIME-complete, whereas the same problems expressed with conventional representations are only P-complete
P-complete
In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:# which problems are difficult to parallelize effectively, and;# which problems are difficult to solve in limited space....
, because the succinct circuit inputs have smaller encodings.
Output-sensitive algorithm
Output-sensitive algorithm
In computer science, an output-sensitive algorithm is an algorithm whose running time depends not only on the size of the input but also on the size of the output...
s define their complexity not only in terms of their input but also their output. For example, Chan's algorithm
Chan's algorithm
In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2 or 3 dimensional space. The algorithm takes O time, where h is the number of vertices of the output...
can compute the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of a set of points in O(n log h) time, where n is the number of points in the input and h is the number of points in the resulting convex hull, a subset of the input points. Because every input point might be in the convex hull, an analysis in terms of the input alone would yield the less precise O(n log n) time.
The complexity of some algorithms depends not only on parameters of the input but also parameters of the machine the algorithm is being run on; as mentioned in #Metric being measured below, this is typical in analyzing algorithms that run on systems with fixed cache hierarchies, where the complexity may depend on parameters such as cache size and block size.
Abstract machine
To analyze an algorithm precisely, one must assume it is being executed by a particular abstract machineAbstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
. For example, on a random access machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
, binary search
Binary search algorithm
In computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
can be used to rapidly locate a particular value in a sorted list in only O(log n) comparisons, where n is the number of elements in the list; on a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, this is not possible, since it can only move one memory cell at a time and so requires Ω(n) steps to even reach an arbitrary value in the list.
Moreover, different abstract machines define different primitive operations, which are operations that can be performed in constant time. Some machines, like Turing machines, only permit one bit at a time to be read or written; these are called bit operations, and the number of bit operations required to solve a problem is called its bit complexity. Bit complexity generalizes to any machine where the memory cells are of a fixed size that does not depend on the input; for this reason, algorithms that manipulate numbers much larger than the registers on ordinary PCs are typically analyzed in terms of their bit complexity. Put another way, the bit complexity is the complexity when the word size is a single bit, where word size is the size of each memory cell and register.
Another commonly-used model has words with log n bits, where n is a variable depending on the input. For example, in graph algorithms, it is typical to assume that the vertices are numbered 1 through n and that each memory cell can hold any of these values, so that they can refer to any vertex. This is justified in problems where the input uses Ω(n) words of storage, since on real computers, the memory cell and register size is typically selected in order to be able to index any word in memory. Operations on these words, such as copies and arithmetic operations, are assumed to operate in constant time, rather than O(log n) time. The number of word operations required to solve a problem in this model is sometimes called its word complexity.
In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, researchers intentionally define complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es in a way intended to make them machine-independent - that is, if a problem lies in a particular class relative to a particular "reasonable" machine, it will lie in that class relative to any "reasonable" machine. For example, as mentioned above, the time complexity of binary search
Binary search algorithm
In computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
depends on whether a Turing machine or a random access machine is used; but regardless of the machine choice, it lies in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, the class of polynomial-time algorithms. In general, P is considered a machine-independent class because any operation that can be simulated in polynomial time can be assumed to require constant time, since it can be treated as a subroutine without exceeding the polynomial-time bound.
Oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
s are machines that have a specific operation that they can perform in constant time; this operation can be arbitrarily complex and can dramatically affect the complexity of algorithms performed on the machine. For example, if one has an oracle to solve any NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem, then any problem in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
can be solved in polynomial time (whereas without the oracle, no polynomial-time algorithm is known for many of these problems). Oracle machines are impractical to construct but useful in theory for determining which proof techniques will be effective.
Metric being measured
It's typical to say without qualification that insertion sortInsertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
requires O(n2) time; however, it doesn't make sense to say that the bit complexity of insertion sort is O(n2), unless the elements being sorted are of constant size. If the elements are assumed to be integers between 1 and n, then the word complexity where words have log n bits would be O(n2), but it's preferable to have a model that allows sorting of lists other than lists of small integers, such as lists of strings. In this case, instead of measuring the number of time steps the abstract machine takes, it's preferable to define a particular metric appropriate to the problem at hand. For comparison sort
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list...
algorithms, which examine the input using only comparisons and modify it using only exchanges (swaps), the typical metric is either the number of element comparisons performed, the number of element exchanges performed, or the sum of these. Different comparison sort algorithms can be compared using these metrics, but for useful comparison with non-comparison sorting algorithms, such as radix sort
Radix sort
In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value...
, a different metric must be used, and the set of elements must be restricted.
Because disk operations are orders of magnitude slower than accesses to main memory, the typical metric used in disk-based algorithms is the number of disk seeks or the number of blocks read from the disk, which depend on both the input and the parameters of the disk. RAM accesses and CPU operations are "free." Similarly, in many models used to study data structures, such as the cache-oblivious model, operations on cached data are considered "free" because they are typically orders of magnitude faster in practice than access to main memory. Consequently, the typical metric used is the number of cache misses, which depends on both the input and parameters of the cache.