Context of computational complexity

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.

Definitions of variables

Metrics are usually described in terms of variables that are a function of the input. For example, the statement that insertion sort requires O(n²) 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 tests and multiplication algorithms 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 Θ(n^1/2) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2^n/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 Θ(n^1/2) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to Θ(2^n/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 graphs 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 algorithms 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.

Abstract machine

To analyze an algorithm precisely, one must assume it is being executed by a particular abstract machine. 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 classes 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 machines 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.

Metric being measured

It's typical to say without qualification that insertion sort requires O(n²) time; however, it doesn't make sense to say that the bit complexity of insertion sort is O(n²), 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(n²), 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.