1
$\begingroup$

I have a simple program which achieves a certain functionality. I’m interested to know if it can be proven that the steps in the program are the theoretically simplest way to achieve those results. Is it an established practice in computer science to prove that an algorithm or program is the theoretically fastest way to do something, or the one with the least steps? Or is it more often that an algorithm is the fastest known, but it’s impossible to know if there’s a faster one?

$\endgroup$
2
  • 2
    $\begingroup$ What is "simplest"? It depends on the problem, but usually we like to minimize the run-time of the algorithm. $\endgroup$
    – nir shahar
    Commented Oct 3, 2021 at 7:30
  • $\begingroup$ I was imagining some kind of useful definition could be found like just the number of distinct “steps”. I mean, in information theory, they say repetition does not carry more information, so a loop would be seen as one entity, no matter how long it ran. Whereas any unitary statement like a variable declaration would count as “more content” in the program. (Perhaps.) $\endgroup$ Commented Oct 3, 2021 at 10:35

1 Answer 1

1
$\begingroup$

It is highly uncommon to prove that a certain algorithm is strictly optimal in any sort of sense. It's usually too much to hope for. For example, consider sorting. How many comparisons are needed to sort a list of $n$ numbers? Only a handful of values are known: this is A036604. What is known is that the optimal number is $\Theta(n\log n)$, and so algorithms such as mergesort are asymptotically optimal, that is, optimal up to a constant factor. (In the particular case of comparison-based sorting, probably more accurate bounds are known, but this is not typical.)

For general algorithms, we run into even more trouble, since it's not entirely clear how to measure the complexity of an algorithm. The number of clock cycles that an algorithm takes is highly dependent on the CPU, for example. Therefore we usually only measure the asymptotic time complexity, and we cannot expect to get optimality results which are more accurate than that, unless measuring something other than running time (for example, space complexity, or a measure such as number of comparisons).

Even worse, proving lower bounds on the complexity of problems is extremely difficult. We only know asymptotically tight lower bounds in highly restricted or structured models, such as comparison-based sorting. It is currently hopeless to determine the asymptotic complexity of any algorithm task which cannot be solved in linear time, in all but a handful of cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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