Editing Computational complexity (section)

==Asymptotic complexity==
{{see also|Asymptotic computational complexity}}
It is generally difficult to compute precisely the worst-case and the average-case complexity. In addition, these exact values provide little practical application, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values of {{mvar|n}}, and this makes that, for small {{mvar|n}}, the ease of implementation is generally more interesting than a low complexity.

For these reasons, one generally focuses on the behavior of the complexity for large {{mvar|n}}, that is on its [[asymptotic analysis|asymptotic behavior]] when {{mvar|n}} tends to the infinity. Therefore, the complexity is generally expressed by using [[big O notation]].

For example, the usual algorithm for integer [[multiplication]] has a complexity of <math>O(n^2),</math> this means that there is a constant <math>c_u</math> such that the multiplication of two integers of at most {{mvar|n}} digits may be done in a time less than <math>c_un^2.</math> This bound is ''sharp'' in the sense that the worst-case complexity and the average-case complexity are <math>\Omega(n^2),</math> which means that there is a constant <math>c_l</math> such that these complexities are larger than <math>c_ln^2.</math> The [[radix]] does not appear in these complexity, as changing of radix changes only the constants <math>c_u</math> and <math>c_l.</math>