World's most popular travel blog for travel bloggers.

# lower bound of checking if in array are two different elements

, ,
Problem Detail:

Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $n-1$. Consider the diagram hasse. This diagram must be consistent (one piece), so you need at least $n-1$ edges (comparisons),.

However, I would like to consider a decision tree. Unfortunately, I can not consider this, look how I think about it.

###### Answered By : Yuval Filmus

Decision tree lower bounds don't quite work here. The obvious way to apply a decision tree lower bound is to consider the output of the algorithm, which is either TRUE or FALSE. Since there are two possible outputs, the decision tree lower bound gives a lower bound of one comparison. Not very helpful.

A more interesting example of the decision tree technique forces the algorithm to output a little more, namely either it outputs YES (all the elements are the same), or a pair of different elements (represented as their indices). You can argue that whenever the algorithm returns NO it actually knows two elements which are different. Considering all inputs of the form $x_1 = \cdots = x_{i-1} = x_{i+1} = \cdots = x_n = 0, x_i = 1$, we see that for each $i$ there must be a leaf of the form $(i,\ast)$. This means that there must be at least $n/2$ NO leaves, resulting in a lower bound of $\log_2(1+n/2)$ on the number of comparisons. This can plausibly be improved to $\log_2(1+\binom{n}{2})$, but both quantities are $\Theta(\log n)$.

The correct way to argue here is using an adversary argument. Consider any algorithm, and trace its execution, always answering YES to any query. Consider the graph whose vertices are all elements (i.e., all indices), and the edges correspond to queries performed by the algorithm. If the graph is not connected, the algorithm can't know whether all elements are the same (indeed, it is consistent both that all elements have the value $0$, or that the elements in the $i$th connected components have the value $i$). Since a connected graph has at least $n-1$ edges, any algorithm must perform as least $n-1$ comparisons. It's not hard to see that this bound is achievable.