Computational complexity: Difference between revisions

Revision as of 02:28, 23 February 2021

Revision as of 09:04, 23 February 2021

Line 31:

==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 desirablelow 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]].