Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted
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 &lt; 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 &lt; v$.
If $a_u &lt; a_v$, our array may still be sorted.
If $a_u &gt; 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 &lt; v$, $a_u &lt; a_v$ in the first case and $a_u &gt; a_v$ in the second case.