Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the
list, and scan along until we first find a successive pair of elements that is out of order. In that case, return
false. If no such pair is found by the time we reach the end of the list, return true.
Our elementary operation is a comparison between two integers.
I'm trying to find the average case running time of this algorithm.
For a permutation with the first $k$ elements sorted and the first $k+1$ unsorted the algorithm must make $k$ comparisons. For each combination of $k+1$ elements out of $n$, there is one in which these $k+1$ elements are sorted. The number of possible permutations of $n$ elements without repetition is $n!$. Therefore the probability that at least the first $k+1$ elements are sorted is: $$\binom{n}{k+1}\cdot\frac{1}{n!}$$
If $K$ is a discrete random variable over the natural numbers 1 to $n-1$ (our event space, since the best case was $k=1$ and the worst case was $k=n-1$), this probability is $\mathbb{P}(K\ge k+1)=\mathbb{P}(K>k) $.
We have that: $$\mathbb{E}[K]=\sum\limits_{k=1}^{n-1}\mathbb{P}(K>k)$$
We also have that:
$$\sum\limits_{k=0}^{n}\binom{n}{k}=2^n$$
$\binom{n}{0}=1$ for all $n$, so $\sum\limits_{k=1}^{n}\binom{n}{k}=2^n-1$. Therefore, if $K$ is the distribution of running times of our algorithm:
$$\mathbb{E}[K]=\sum_{k=1}^{n-1}\Bigg[\binom{n}{k+1}\cdot\frac{1}{n!}\Bigg]=\frac{1}{n!}\sum_{k=1}^{n-1}\binom{n}{k+1}=\frac{1}{n!}\sum_{k=2}^{n}\binom{n}{k}=\frac{1}{n!}\Bigg(\sum_{k=1}^{n}\binom{n}{k}-\binom{n}{1}\Bigg)=
$$
$$
=\frac{1}{n!}\Bigg(2^n-1-\frac{n!}{1!(n-1)!}\Bigg)=\frac{2^n-n-1}{n!}
$$
However, this gives nonsensical values. It should be that for all $n<0$ and $n\in\mathbb{N}, \mathbb{E}[K]\ge1$, since the algorithm must check at least the first pair of elements. However, this function for the expected value does not satisfy this.
I can't see where I've gone wrong, but I must have. What have I done incorrectly?
Best Answer
Suppose that the first $k$ elements are sorted, but the first $k+1$ are not. There are $\binom{n}{k+1}$ ways to choose the first $k+1$ elements. They can be permuted in $(k+1)!$ ways, but only $k$ of these permutations have the desired property. The remaining $n-k-1$ elements can be permuted in $(n-k-1)!$ ways, so there are
$$k(n-k-1)!\binom{n}{k+1}=\frac{kn!}{(k+1)!}$$
permutations in which the first $k$ elements are sorted, but the first $k+1$ are not. Thus,
$$\Bbb P(K=k)=\frac{k}{(k+1)!}$$
for $1\le k\le n-2$. For $k=n-1$, however, a small correction is needed: we’ll have $K=n-1$ both when the list is sorted except for the last element and when it’s completely sorted, so
$$\Bbb P(K=n-1)=\frac{n}{n!}=\frac{n-1}{n!}+\frac1{n!}\;,$$
and
$$\begin{align*} \Bbb E[K]&=\frac{n-1}{n!}+\sum_{k=1}^{n-1}\frac{k^2}{(k+1)!}\\ &=\frac{n}{n!}-\frac1{n!}+\sum_{k=2}^n\frac{(k-1)^2}{k!}\\ &=\frac1{(n-1)!}-\frac1{n!}+\sum_{k=2}^n\frac{k^2}{k!}-2\sum_{k=2}^n\frac{k}{k!}+\sum_{k=2}^n\frac1{k!}\\ &=\frac1{(n-1)!}+\sum_{k=2}^n\frac{k}{(k-1)!}-2\sum_{k=2}^n\frac1{(k-1)!}+\sum_{k=2}^{n-1}\frac1{k!}\\ &=\sum_{k=1}^{n-1}\frac{k+1}{k!}-2\sum_{k=1}^{n-2}\frac1{k!}+\sum_{k=2}^{n-2}\frac1{k!}\\ &=\sum_{k=1}^{n-1}\frac1{(k-1)!}+\sum_{k=1}^{n-1}\frac1{k!}-\frac2{1!}-\sum_{k=2}^{n-2}\frac1{k!}\\ &=\frac1{0!}+\sum_{k=1}^{n-2}\frac1{k!}+\frac1{1!}+\frac1{(n-1)!}-2\\ &=\sum_{k=1}^{n-1}\frac1{k!}\;. \end{align*}$$
As a quick and dirty check, for $n=2$ we have $\Bbb E[K]=1$, which is clearly correct, and for $n=3$ we have $\Bbb E[K]=\frac32$, which is easily verified by direct computation: the permutations $123,132$, and $231$ have $K=2$, and the permutations $213,312$, and $321$ have $K=1$.
The sequence $$a_n=n!\sum_{k=1}^{n-1}\frac1{k!}$$ is OEIS A038156 and apparently has the closed form
$$a_n=\lfloor (e-1)n!\rfloor-1\;.$$