1
$\begingroup$

Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ and $0s$.

Decision tree give us lower bound $\log(n+1)$. It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least $n-1$ comparisons. If it is lower bound ? I don't, but I think that it is $n$.

Why Do I think that lower bound is equal to $n$ ?

Let consider array $|a|=n$ such that $a[1]=a[2]=...=a[n-1]=0$ and $a[n]=1$.

It is needed at least $n-2$ comparisons to check that there is $n-1$ equal elements. And additional $2$ comparisons to check that $1$ is greater then rest of elements.

What is it real lower bound? What about my justification ?

Edit: We assume model computation as comparison $\le$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Are you allowed to query the elements or only to compare them? $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 16:23
  • 1
    $\begingroup$ The argument showing that $n-1$ comparisons are needed for computing the minimum also works here (the one where you show that the comparison graph must be connected). This is tight since it suffices to compare the first element to all other elements. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 16:27
  • $\begingroup$ I know that we must do at least $n-1$ comparisons, but it is lower bound ? $\endgroup$
    – user40545
    Commented Nov 7, 2015 at 17:06
  • 1
    $\begingroup$ That's the meaning of lower bound - you need to make at least some number of comparisons. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 20:44
  • 1
    $\begingroup$ What do you mean by "we may use comparison = or <"? Do you mean that you can either ask a query of the form $a=b$, or a query of the form $a<b$? If so, this is not so clear from the way you wrote it. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 22:26

1 Answer 1

Reset to default
1
$\begingroup$

$n-1$ comparisons are necessary and sufficient. To show that $n-1$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most $n-2$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most $n-2$ edges, it is not connected. Let $C_1,C_2$ be two connected components. It is consistent that the value of all elements in $C_1$ is $0$ and that the value of all elements in $C_2$ is $1$. It is also consistent that all elements in $C_1$ are $1$ whereas all elements in $C_2$ are $0$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that $n-1$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:

  1. The first element is equal to all other elements. In this case the array is already sorted.

  2. The first element equals the elements in $S$ and is smaller than the elements in $T$. Thus the first element and the elements in $S$ have the value $0$ and the elements in $T$ have the value $1$, and we can sort the array accordingly.

  3. The first element equals the elements in $S$ and is larger than the elements in $T$. This is symmetric to the previous case.

Improve this answer
$\endgroup$
14
  • 1
    $\begingroup$ You're right, a simpler proof would use a reduction from the problem of finding the minimum. In fact this adversary argument is also identical to the one used to prove the lower bound for minimum. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 22:27
  • 1
    $\begingroup$ Regarding your other comment – I answered the question as first posed, and leave the new question for you to solve. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 22:28
  • 1
    $\begingroup$ @user40545 I don't. $\endgroup$
    – Yuval Filmus
    Commented Nov 7, 2015 at 23:05
  • 1
    $\begingroup$ @user40545 I explained in the answer. $\endgroup$
    – Yuval Filmus
    Commented Nov 8, 2015 at 5:44
  • 1
    $\begingroup$ @user40545 I know that $a[1]=a[4]=a[5]$ and that $a[1]>a[2],a[3],a[6]$. $\endgroup$
    – Yuval Filmus
    Commented Nov 8, 2015 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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