**Problem Detail:**

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$.**

###### Asked By : user40545

#### Answered By : Yuval Filmus

$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:

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

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.

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

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49193

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback