How can I prove that any comparison based algorithm that checks whether a given n-element sequence is sorted performs at least $(n-1)$ comparisons in its worst case?
I know Insertion sort and Bubble sort make $n-1$ comparisons, but how do I prove this for all comparison based algorithm?
You can imagine the $n$ elements to be paired as vertices in a graph. Every time you compare two elements, you draw an edge between them.
The idea is that without drawing at least $n-1$ edges, you cannot be sure the sequence is actually sorted. If there were less than $n-1$ edges, then the graph would have at least two distinct connected components. Then the algorithm would not be sure what the correct order of those two connected components is in the list.