4
$\begingroup$

I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case.

I have no idea how to prove that it is optimal in terms of the number of comparisons. The only argument which came up to my mind is that we of course have to read the whole array, but I don't think it is a proper argument. I tried to use argument similar to minimal number of comparisons to find minimum (with graph), but it doesn't seem to be good in that case.

How can I prove that $n$ comparisons is optimal in the worst case?

$\endgroup$
  • $\begingroup$ You cannot prove that because you can use only $n-1$ comparisons... Anyway to prove that $n-1$ comparisons is the minimum you probably have to work for contradiction. Assume an algorithm always take at most $n-2$ comparisons. Find a counterexample that it can always return the correct result. $\endgroup$ – Bakuriu Mar 19 '16 at 15:37
  • 1
    $\begingroup$ Are You sure n-1 is enough? Could you show me algorithm for example: 1,2,3,4,5,6,7,9,10,8 ? $\endgroup$ – Michocio Mar 19 '16 at 19:25
  • 1
    $\begingroup$ It's meaningless to ask for an algorithm for a specific example. I can write such an algorithm that uses no comparisons at all. $\endgroup$ – Yuval Filmus Mar 20 '16 at 17:08
2
$\begingroup$

To show that the optimal number of comparisons is $m$, you have to prove that any algorithm that uses $m-1$ comparisons must make a mistake on some arrays. The usual way to accomplish that is through an adversary argument – you "react" to the queries of the algorithm in a specific way, and ensure that after $m-1$ steps, there are two different linear orders that are consistent with your answers to the queries (as well as comply with the constraints – in this case at most two inversions).

$\endgroup$

Your Answer

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

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