28
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$
    – greybeard
    Commented Feb 16, 2020 at 23:20
  • $\begingroup$ 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"? $\endgroup$
    – Rhyous
    Commented Mar 5, 2020 at 20:04
  • $\begingroup$ @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. $\endgroup$
    – Juho
    Commented Mar 5, 2020 at 21:18

2 Answers 2

Reset to default
35
$\begingroup$

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.

Improve this answer
$\endgroup$
0
3
$\begingroup$

I've seen this concept explained as Solomonoff induction, a formalization of Occam's razor.

Given some set of Turing machines that fit the data, the one with the lowest complexity is likely to be the one that truly models it.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.