Content deleted Content added
Question about statement in article. |
Deltahedron (talk | contribs) the maximum time isn't a useful concept -- although it can be thought-provoking, see Bogosort for example |
||
Line 466:
== Computational complexity ==
[[Computational_complexity_theory#Upper_and_lower_bounds_on_the_complexity_of_problems|Upper_and_lower_bounds_on_the_complexity_of_problems]], begin with stating that "''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. The complexity of an algorithm is usually taken to be its worst-case complexity''" Shouldn't it be the maximum amount of time?--[[User:Natematic|Natematic]] ([[User talk:Natematic|talk]]) 17:55, 18 November 2012 (UTC)
: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)
| |||