1
$\begingroup$

Determine the worst-case complexity (in number of comparisons of two array elements) that allow you to conclude that a given array with n elements is not sorted.

I sort of have a general idea of what is going on. Suppose I have two element array, then make one comparison between these two elements.

If I have three elements, then i compare the 0th index element with 1st index element, sort it, and then compare 2nd index element with whatever is now the 1st element after sorting. Hence, I obtain 2 total comparisons.

Going on this pattern, I believe I will make n-1 comparisons which becomes my worst-case complexity. But of course, this is not a proof. How can I make this mathematically rigorous? Am I on right track?

$\endgroup$
  • $\begingroup$ Are you familiar with adversary arguments? This is the technique used to prove such claims. $\endgroup$ – Yuval Filmus Jul 4 '18 at 5:54
  • $\begingroup$ Your question isn't completely clear – one comparison suffices to conclude that an array isn't sorted. The more interesting question is how many comparisons are needed to conclude that the array is sorted. $\endgroup$ – Yuval Filmus Jul 4 '18 at 5:55
0
$\begingroup$

The minimum number of comparisons to tell whether an $n$-element array is sorted is indeed $n - 1$. However, we don't have to sort the array to arrive to a conclusion.

Here is how to check an array $a$ in $n - 1$ comparisons. Compare $a_0$ to $a_1$, compare $a_1$ to $a_2$, ..., compare $a_{n-2}$ to $a_{n-1}$. If all comparisons result in "less or equal" outcome, the array is sorted. If any comparison results in "greater" outcome, the array is not sorted. Here, "sorted" means "the elements follow in non-decreasing order from left to right".

The harder thing is to prove that less comparisons won't be enough. Sure, if we just followed the above checks but dropped the last one, we won't know whether $a_{n-2} \le a_{n-1}$ holds, so the array is sorted if it does but is not sorted if it doesn't. But what if we compared some other $n - 2$ pairs?

One way to prove it is to establish and maintain some global characteristic of our knowledge about comparison results. Namely, consider a graph where vertices are array indices: $0$, $1$, $2$, $\ldots$, $n-1$. The edges of the graph will be the comparisons we make.

As we add our edges, let us track such global characteristic: the number of connected components in the graph. Initially, it is $n$, same as the number of vertices. Each edge either lies inside some component, or connects two different components, so the number of components drops by at most $1$ with each edge added.

In the end, after $n - 2$ edges, we will have at least $2$ connected components. Let all comparisons for vertices $i < j$ so far result in $a_i \le a_j$, so that the result is still unknown. Consider any vertex $u$ from one of them and any vertex $v$ from another, such that $u < v$. If $a_u < a_v$, our array may still be sorted. If $a_u > a_v$, it is not sorted.

Either of the above does not contradict any prior information about the array, so both are possible, which concludes our proof. If that's unconvincing, we can construct the example arrays. For the first case, simply let $a_i = i$, which is clearly a sorted array. For the second case, let $a_i = i$ for all elements of the $v$'s connected component, and let $a_i = i + n$ for all other indices. We can check that both arrays are consistent with our $n - 2$ comparisons, and for two vertices $u < v$, $a_u < a_v$ in the first case and $a_u > a_v$ in the second case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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