# Reasoning on Efficiency

It is possible to prove the correctness of algorithms, and two algorithms can be compared to see which has better performance using $O$ and $o$ notation.

Is it possible to prove the efficiency of an algorithm? I.e. That that algorithm is the most efficient possible algorithm for a problem.

Let $K_i$ be the set of all algorithms(both known and unknown) for solving a particular problem $P_i$ $$K_i = [A_{i1}, A_{i2}, ... ,A_{in}]$$

Is it possible that given an Algorithm $A_{ij}$, one can prove that $$\forall A_{ix} \in K_i, A_{ij} = o(A_{ix})$$

If the answer is yes, is there a known method to do this?

• How is this different from your follow-up question? – Yuval Filmus Dec 8 '16 at 14:46
• You must specify the model of computation for this. – Juho Dec 8 '16 at 15:09