# Average case complexity for checking if list is sorted

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. Suppose that the input list is a random permutation of $1, 2, \ldots, N$ and all such permutations are equally likely. Derive the average-case expected running time. Give both an exact and asymptotic answer.

The complexity for a given list depends on when the first pair of out-of-order elements are encountered. Let $c_N\left(n\right)=n$ be the complexity for a list where the $n$th pair is the first that is out-of-order.

Let $p_N\left(n\right)$ be the probability that the $n$th pair of the list is the first that is out-of-order.

Then I understand that the average case complexity is given by $\sum_{n=1}^{N-1} p_N\left(n\right)c_N\left(n\right) + \left(1 - \sum_{n=1}^{N-1} p_N\left(n\right)\right) \left(N-1\right)$.

However, I have been struggling to derive $p_N\left(n\right)$. By hand-working a number of examples, I have identified that $p_N\left(n\right) = \frac{1}{a\left(n\right)}$, where $a\left(n\right) = n! + \left(n-1\right)!$ is the sequence A001048.

I have tried to reverse-engineer a derivation by recognising that $p_N\left(n\right) = \frac{f_N\left(n\right)}{N!}$, where $f_N\left(n\right)$ is the number of lists whose $n$th pair is the first that is out-of-order. Algebra shows that $f_N\left(n\right) = n \frac{N!}{\left(n+1\right)!}$ but unfortunately I cannot see how this term would be derived.

I would appreciate any hints. Thank you in advance for your help!

P.S. I have also discovered via WolframAlpha the interesting property that $\sum_{n=1}^\infty p_N\left(n\right)c_N\left(n\right) = e - 1$.

## 1 Answer

There are $\binom{N}{n+1}$ ways to choose the first $n+1$ elements of the list. There are exactly $n$ ways to order these so that the only pair out of order is the last pair: we must pick one of the $n$ elements other than the largest, put it at the end, and precede it by the remaining $n$ elements in increasing (i.e., sorted) order. Finally, there are $(N-n-1)!$ ways to permute the remaining elements of the list. Thus,

$$f_N(n)=n\binom{N}{n+1}(N-n-1)!=\frac{nN!(N-n-1)!}{(n+1)!(N-n-1)!}=\frac{nN!}{(n+1)!}\;.$$

• Thank you; that is very helpful! I wish I could have seen it myself, but I am glad to know that I was on the right track :) – nimble agar Mar 30 '15 at 8:00
• @Arman: You were indeed. You’re welcome! – Brian M. Scott Mar 30 '15 at 8:01