Content deleted Content added
m Task 18 (cosmetic): eval 6 templates: hyphenate params (4×); |
IznoRepeat (talk | contribs) m →Others: invert math-link placement for upcoming tstyles |
||
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.
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
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.
| |||