2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – chausies Jan 22 at 8:54
  • $\begingroup$ @chausies, oh! Right! Thank you so much for the fix! $\endgroup$ – D.W. Jan 22 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.