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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.