HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is there an algorithm for algorithms time/space complexity optimisation?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
spaceoptimisationtimealgorithmsalgorithmfortherecomplexity

Problem

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of algorithms?

For example an implementation of bubble sort as an input for such an algorithm would produce an implementation of a sorting algorithm with time complexity closer to $O(n\log n)$.

Solution

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data.

By Rice's theorem, it is impossible to know if two given programs do the same job.

Yes, for some very restricted notions of "program", given an example one can construct the "best possible" program for the job. Important classes, even. But a very far cry from anything which is able to express bubblesort.

Context

StackExchange Computer Science Q#51516, answer score: 11

Revisions (0)

No revisions yet.