1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 22, 2022 at 6:13
  • 1
    $\begingroup$ Why do you think you are wrong to say that the graph is connected? Try working through some examples for small values of $n$. $\endgroup$
    – D.W.
    Jan 22, 2022 at 6:13
  • $\begingroup$ @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. $\endgroup$
    – user624
    Jan 22, 2022 at 6:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – benrg
    Jan 23, 2022 at 21:51
  • 1
    $\begingroup$ Isn't it trivial that if not all elements are equal, then there is a pair of consecutive elements that are different (and reciprocally) ? $\endgroup$
    – user16034
    Jun 24, 2022 at 8:13

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Feb 24, 2022 at 1:44
  • $\begingroup$ @Pseudonym the question as stated is prove there is an algorithm, not prove that algorithm is optimal though isn't it? $\endgroup$ Feb 24, 2022 at 1:48
  • $\begingroup$ Ah, yes, true. Proving that it's optimal is a little trickier. $\endgroup$
    – Pseudonym
    Feb 24, 2022 at 6:58
1
$\begingroup$

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

$\endgroup$

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.