I have a simple algorithm to check if a series of numbers is sorted: if the first two numbers are sorted, move to the next two. Else, stop and return false. I want to figure out the average case running time of this algorithm if the possible inputs are random permutations of $n$ objects, $n$ objects chosen, and each permutation is equally likely - I'm using numbers 1 to $n$.
I'm struggling with trying to figure out the number of permutations that will require $x$ comparisons. I have figured out that the worst case, $x=n-1$, can happen for $n$ different permutations.
The best case ($x=1$) was a little more complicated - the first number could be any but 1, the second any number smaller than $n$, and the remaining numbers could be any of the remaining. This gave me: $$[\sum_{i=2}^n(i-1)](n-2)!$$ which I could expand to $n!\over 2$.
For $x=2$, the first number could be any except the largest, the second any larger than the first, and the third any smaller than the second, and the rest any of the remaining numbers. This gave me: $$[\sum_{i=1}^{n-1}\sum_{j=i}^n(j-2)](n-3)!$$ This seems quite clumsy to me, and I am no closer to having a probability distribution. Is there a simpler, tidier way to find out the number of permutations of $n$ items which require $x$ comparisons?
Here's the way that I am thinking about the problem, I hope it helps and makes sense.
If the algorithm breaks after $x$ steps, then the first $x$ elements are in increasing order... and element $x+1$ is smaller than element $x$. The number of permutations that have the first $x$ elements in increasing order is $\binom{n}{x}(n-x)!$ because once the first $x$ elements are chosen their order is determined, and there are $(n-x)!$ ways to fill in the remaining elements. Now, the trickier part is counting how many of these permutations have element $x+1$ smaller than element $x$. We don't want to try to compute this directly (that would be quite hard). Instead, lets just subtract the number of permutations that have the first $x+1$ terms in increasing order. There are $\binom{n}{x+1}(n-x-1)!$ of those. So the total number of permutations that break after exactly $x$ steps is:
$$\binom{n}{x}(n-x)! - \binom{n}{x+1}(n-x-1)!$$