Content deleted Content added
Deltahedron (talk | contribs) the maximum time isn't a useful concept -- although it can be thought-provoking, see Bogosort for example |
No edit summary |
||
Line 468:
:The complexity is the minimum time required, the running time of the most efficient algorithm. It is possible to spend as much time as you like on solving a problem, so the maximum time isn't a useful concept -- although it can be thought-provoking, see [[Bogosort]] for example. The worst case is the maximum of those minimum times, in other words the greatest length of time you can be compelled to spend even doing it as quickly as possible. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 18:26, 18 November 2012 (UTC)
::I agree with you. My point is: if you say "''one is interested in proving upper and lower bounds on the '''minimum''' amount of time required by the most efficient algorithm solving a given problem''", I get that considering the most efficient algorithm, you say that the complexity is the time it spend in its best-case. In other words, it seems to me that the best-fitting formalization for that proposition above is <math>\min \{time(T(x))\}_{x\in X}</math> where <math>X</math> is the set of possible input and <math>T</math> is the most efficient algorithm.
| |||