Content deleted Content added
Undid revision 1061050031 by D.Lazard (talk) Removed dubious statement for which no WP:RELIABLE was given. |
m Put in separate heading for "Big Complexity" so it can be directly linked to from the "Time Complexity" page. |
||
Line 22:
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''<sup>~</sup>(''n''<sup>4</sup>)]]}}.
===Bit Complexity===
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
| |||