# If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $$n$$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list). What I'm left with is a shorter list that's guaranteed to be in-order.

Example: The starred elements of this list would be deleted during the walk through.

[1, 4, 2*, 3*, 5, 7, 6*] -> [1, 4, 5, 7]

My question is: On average, what will be the length of the remaining list? And is there some simple/obvious form of the distribution of this?

And as one follow-up: if we used this for a sorting algorithm (called Drop Sort), what would the run-time be? To be clear, the algorithm would be something like this: $$\textit{DropSort}(\text{list}) = \textit{Merge}(\text{Remaining list}, \textit{DropSort}(\text{Rejected list}))$$

This question was inspired by this r/ProgrammerHumor post.

You can compute the average using linearity of expectation.

Let the random variable $$X$$ denote the number of elements that are retained. Let $$X_i$$ be an indicator r.v. that is 1 if the $$i$$th element is retained, or 0 otherwise. Then $$X = X_1+\dots + X_n$$, so

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$

Now the $$i$$th element is retained if and only if it is the largest number among the first $$i$$ elements in the list. Therefore, $$\Pr[X_i=1]=\frac{1}{i}$$, so

$$\mathbb{E}[X] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma$$

In other words, the average length of the remaining list is $$O(\log n)$$.

I don't know what the distribution is.

As a heuristic, the expected running time of Drop Sort would satisfy a recurrence something like $$T(n) \approx T(n-\log(n)) + O(n)$$, which corresponds to $$O\left(\frac{n^2}{\log n}\right)$$ time.

• Fantastic! Just a small error, though. The probability of being the max is $1/i$, not $1/i!$, which would lead to $\log n$. Submitted an edit! – chausies Jan 22 at 8:54
• @chausies, oh! Right! Thank you so much for the fix! – D.W. Jan 22 at 8:56