Content deleted Content added
Undid revision 1109200915 by 72.174.131.123 (talk) the fact that the time is standardly measured in elementary operation is explained in the article and deserve to be mentioned here, but is too technical for the |
→Others: typo |
||
Line 30:
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>)]]}}.
In [[sorting]] and [[search algorithm|searching]], the resource that is generally considered is the number of
==Complexity as a function of input size==
| |||