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

Is there a name for the class of algorithms that are the most efficient for a particular task?

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

Problem

This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.

We would therefore have to be able to show that any other algorithm is at best of the same order of complexity as the algorithm in question.

I'm asking because I'm working on a paper that makes use of this concept, and I was surprised when I realized that I'm not aware of any name for this concept, though I'll concede I'm risking embarrassment if there is such a name that I'm simply unaware of.

Solution

You can say that an algorithm is asymptotically optimal in such a case.

In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.

Context

StackExchange Computer Science Q#120810, answer score: 34

Revisions (0)

No revisions yet.