This site is supported by donations to The OEIS Foundation.
Algorithmic analysis
There are no approved revisions of this page, so it may not have been
Contents
Algorithmic complexity
(...)
Computational complexity analysis
In computational time complexity analysis, the goal is to solve a problem with a [time] optimal algorithm, an algorithm that has the shortest worst case running time.
Computational simplexity analysis
In computational time simplexity analysis, the goal is to solve a problem with a [time] pessimal algorithm, an algorithm that has the longest best case running time, while having all time spent making progress towards the solution (everything the algorithm does must contribute to the solution).
The simplexity of a problem is the maximum inefficiency among the reluctant algorithms that solve P. An algorithm is said to be pessimal for a problem P if the best-cast [sic] inefficiency of A is asymptotically equal to the simplexity of P.[1]
Intuitively, a reluctant algorithm for a problem P is one which wastes time in a way that is sufficiently contrived to fool a näive [sic] observer.[1]
Notes
- ↑ 1.0 1.1 Andrei Broder and Jorge Stolfi, Pessimal Algorithms and Simplexity Analysis, (1986).
