Computational complexity: Difference between revisions

Revision as of 00:28, 16 May 2021

Revision as of 17:36, 9 June 2021

Line 19:

The number of [[arithmetic operations]] is another resource that is commonly used. In this case, one talks of '''arithmetic complexity'''. If one knows an [[upper bound]] on the size of the [[binary representation]] of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.

{{anchor|bit complexity}}

For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called [['''bit complexity]]''' in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the [[determinant]] of a {{math|''n''×''n''}} [[integer matrix]] is <math>O(n^3)</math> for the usual algorithms ([[Gaussian elimination]]). The bit complexity of the same algorithms is [[exponential function|exponential]] in {{mvar|n}}, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with [[modular arithmetic|multi-modular arithmetic]], the bit complexity may be reduced to {{math|[[soft O notation|''O''^~(''n''⁴)]]}}.

Formally, the ''bit complexity'' refers to the number of operations on [[bit]]s that are needed for running an algorithm. With most [[models of computation]], it equals the time complexity up to a constant factor. On [[computer]]s, the number of operations on [[machine word]]s that are needed is also proportional to the bit complexity. So, the ''time complexity'' and the ''bit complexity'' are equivalent for realistic models of computation

In [[sorting]] and [[search algorithm|searching]], the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized.