# Is it common to prove that some code is the simplest way to achieve something?

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?

• What is "simplest"? It depends on the problem, but usually we like to minimize the run-time of the algorithm. Commented Oct 3, 2021 at 7:30
• 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.) Commented Oct 3, 2021 at 10:35

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.)