Hacker News new | past | comments | ask | show | jobs | submit login
Pessimal Algorithms and Simplexity Analysis (1984) [pdf] (mipmip.org)
33 points by signa11 on Aug 10, 2016 | hide | past | favorite | 3 comments

The Jules Verne references were the funniest part to me.

But it's definitely an interesting and intriguing, if totally useless, question: What is the slowest possible algorithm for a problem that "doesn't waste time"?

As much as I love Slowsort, it is an inefficient mergesort, so you could argue that it does indeed waste time on a sub-routine. On the other hand, the tree numbering cannot be made more efficient by replacing a part of the algorithm with something smarter, so I’d say it’s the better pessimal algorithm.

That said, Slowsort is still my favourite, for it has all the properties of a good sorting algorithm: stable, easy to parallelize, easily proven correct, easily made in-place.


I think one way to make the question well formulated is to have a series of primitives, each of which has some chance to get to the end of the algorithm. The "best" algorithm is the one generating the longest expected sequence of primitives from a given problem.

Without that, it doesn't seem like there's really an answer to the problem since a program can go indefinitely slow by mixing-in all manner of extra work.

Anyway, a real world analogy is walking through a mine-field - obviously, the aim to not find a land mine as many "search" actions as possible.

Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact