# Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question:

Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers.

We use an algorithm that loops through all the elements in the array, comparing Ai with Ai+1 to check if both are equal, where 0 <= i < n. If there exists some i, such that Ai+1 != Ai, the algorithm returns false. Otherwise, for all i, Ai = Ai+1, hence the algorithm outputs true.

Construct a graph G on n nodes where nodes i and j are adjacent iff the algorithm compares Ai and Aj. Since the algorithm makes n-1 comparisons, there are n-1 edges with n nodes in G, ehnce the graph is connected. With a connected graph, the algorithm will always return the correct ouput as for any i, j indices of the array, Ai and Aj will be directly (or indirectly) compared with each other. Making more than n-1 comparisons simply adds more edges to G, and does not change the fact that the graph is already connected with only n-1 edges, hence the output of the algorithm will not change.

Therefore, there is an algorithm described above that needs at most n-1 comparisons to check if n-element array contains all equal elements.

This is my attempt at a proof, but I am sure that the part on the graph being already connected is wrong. Can someone help me correct my proof?

• We don't check/grade answers here. See here and here. The site format works better if you have 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 same problem you happen to be working on.
– D.W.
Commented Jan 22, 2022 at 6:13
• Why do you think you are wrong to say that the graph is connected? Try working through some examples for small values of $n$.
– D.W.
Commented Jan 22, 2022 at 6:13
• @D.W I am not sure how to explain how making more then n-1 comparisons won't change the result of the algorithm, which is the main part of the proof. Commented Jan 22, 2022 at 6:19
• You only have to prove the correctness of your algorithm, not every conceivable algorithm. Your algorithm never makes more than $n-1$ comparisons, so you don't need to consider what happens when it makes more. Commented Jan 23, 2022 at 21:51
• Isn't it trivial that if not all elements are equal, then there is a pair of consecutive elements that are different (and reciprocally) ?
– user16034
Commented Jun 24, 2022 at 8:13

How about considering proof by induction.

1. Given an array with 2 elements we make one comparison of those two elements, they are either the same or they aren't.

2. We assume that there exists an algorithm that that needs at most n-1 comparisons to check if n element array has all equal elements. So let's consider what happens with an n+1 element array. We can establish that the first n elements are identical (or not) by using at most n-1 comparisons and if they are identical we need one further comparison to check the n+1th element against any of the other n elements, thus we need at most n - 1 + 1 = n comparisons.

• Be careful with this kind of argument. It's not necessarily obvious that an optimal algorithm to test $n$ elements for equality is to test $n-1$ elements and then test the last one. If you made the same claim about sorting, it would "show" that $O(n^2)$ comparisons are needed to sort $n$ items. Commented Feb 24, 2022 at 1:44
• @Pseudonym the question as stated is prove there is an algorithm, not prove that algorithm is optimal though isn't it? Commented Feb 24, 2022 at 1:48
• Ah, yes, true. Proving that it's optimal is a little trickier. Commented Feb 24, 2022 at 6:58

Let a sequence of $$n$$ elements. If all pairs of consecutive elements are equal, then by transitivity all elements are equal. By contradiction, if they are not all equal, then there is certainly a pair of consecutive elements that differ.

Hence

$$\bigwedge_{i=0}^{n-1} (A_i=A_{i+1})$$ settles the query, in $$n-1$$ comparisons. This proves the existence claim.

On another hand, a binary relation (such as equality) can only reduce by one the number of equivalence classes. This proves optimality of $$n-1$$.