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

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.

• I think I have seen a lower bound on the number of primitive operations to solve a problem called that problem's complexity (e.g., $O(l\log n)$ for ordering using key comparison). – greybeard Feb 16 '20 at 23:20
• The term "most efficient" needs clarifying. A computer might be able to do a huge calculation in minutes with a Big O(1) for processor algorithm but doing so requires Big O(n) memory which could be 100 TB. Whereas to do the same calculation on a system that only has 4GB of memory, the processor algorithm might be Big O(n) and the memory algorithm might be Big O (1) yet the calculation will take a day. Which is "most efficient"? – Rhyous Mar 5 '20 at 20:04
• @Rhyous With big Oh, we care about theory not practice. Also, the OP has defined we care about the asymptomatic runtime (number of steps). It's perfectly clear. – Juho Mar 5 '20 at 21:18