2
$\begingroup$

so I need to prove the following:

Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.

The problem comes with the following hint:

Assume an algorithm exists that always correctly tests if the array is sorted using at most $n-2$ comparisons and show there must exist an input where this algorithm fails.

Base on the hint, I tried proving this via contradiction and here is my attempt:

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons. Then, let A be an array of 2 random numbers $a$ and $b$. Given that we don't know the value of $a$ with relation to $b$ or vice versa, in order to find this relation, an thus find out if the array with n-distinct elements is sorted in increasing order, 1 comparison operation, namely between $a$ and $b$, is needed, but then $n-2 = 1-2 \neq 1$. Therefore we have arrived at a contradiction.

While this attempt is most likely wrong, I am somewhat familiar with proofs by contradiction, but I don't see how deriving a contradiction from my initial assumption (the one from the hint) helps prove that $n-1$ comparisons are necessary.

$\endgroup$
  • $\begingroup$ This only proves that when $n=2$ you need at least $n-1$ comparisons. What the exercise asks you to prove is that for every $n$ at least $n-1$ comparisons are needed. $\endgroup$ – Yuval Filmus Mar 4 '17 at 13:30
  • $\begingroup$ You can use simple adversary argument technique to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i = 0, 1, \ldots n-2$. $\endgroup$ – hengxin Mar 4 '17 at 13:31
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Mar 4 '17 at 13:32
  • $\begingroup$ I edited my question a bit, but not sure if this is enough. Should I remove my initial attempt from the question? $\endgroup$ – P. Jhon Mar 4 '17 at 13:49
  • 1
    $\begingroup$ I started an answer, then I figured out you want to restrict this to algorithms that compare array elements and decide which element to compare next based on the outcomes of all previous comparisons (and nothing else). $\endgroup$ – gnasher729 Mar 4 '17 at 23:46
3
$\begingroup$

You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i=0,1, \ldots, n−2$.

If it is not the case, you can carefully choose the values such that $a_{i+1} < a_{i}$, without violating any other comparison results.

You are encouraged to fill the details.

$\endgroup$
0
$\begingroup$

For any $n \geq 1$, $n-1$ comparisons are sometimes necessary to test whether an array with n distinct elements is sorted in increasing order. An adversary argument will be used to prove this.

Suppose we have an array $A$ consisting of elements $a_i, a_{i+1}...a_n$ with $a_i = i$ for $i=1$ to $n$.

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons, and returns true if the algorithm is sorted in increasing order and false if it is not. Now suppose that the algorithm is run on array A. Then since $n-2$ comparisons are performed and the array contains $n-1$ pairs of consecutive elements, there must be a pair of consecutive elements which has not been compared to one another. Note that since $a_i = i$ for every element of the array, the array is indeed sorted in increasing order and the algorithm will return true.

Following, suppose we find element $a_i$ which was not compared to its successor by the algorithm and change its value to $i+2$ (previously $i$), and run the algorithm on array A. Then A is not sorted in increasing order anymore,since $a_i = i+2 > a_{i+1} = i + 1$. but, since $a_i$ is never compared to $a_{i+1}$ the algorithm will still return true, which is incorrect.

$\endgroup$
  • 1
    $\begingroup$ It's not true that there exists an element which has not been compared. It suffices to use $n/2$ comparisons in order to compare all elements. $\endgroup$ – Yuval Filmus Mar 4 '17 at 15:50
  • $\begingroup$ Could you explain that further? $\endgroup$ – P. Jhon Mar 4 '17 at 16:11
  • $\begingroup$ Suppose that $n$ is even. Compare 1,2; 3,4; 5,6; ...; $n-1,n$. Using only $n/2$ comparisons, you have accessed every element. $\endgroup$ – Yuval Filmus Mar 4 '17 at 16:13
  • $\begingroup$ So then, I guess I need to explicitly mention that you need to compare every element with its successor in order to fix it? $\endgroup$ – P. Jhon Mar 4 '17 at 16:16
  • $\begingroup$ You need to come up with a valid proof. $\endgroup$ – Yuval Filmus Mar 4 '17 at 16:18

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.