3
$\begingroup$

Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$? Or equivalently, how quickly can we find

$$ \underset{i}{\arg\max} \; \# \{j \mid a_j > a_i, i < j \le n \} $$

Can it be done in less than $\Omega(n\,\lg n)$ comparisons in the worst case?

A $\Theta(n\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.

$\endgroup$
2
$\begingroup$

No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs.

$$k+1,\:k+2,\:k,\:k+2,\:k-1,\:k+2,\:\ldots,\:2,\:k+2,\:1,\:k+2,\:x_1,\:x_2,\:\ldots,\:x_k$$

Note that, for $a\in\{1,\:2,\:\ldots,\:k+1\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ copies of $k+2$, then a subsequence of $x_1,x_2,\ldots,x_k$. It is not profitable to begin anywhere else, since the maximum bounded subsequence beginning with $k+1$ has length at least $k+2$.

Let the adversary in this lower bound choose a random permutation $\pi$ on $\{1,2,\ldots,k\}$ and answer as though $x_j=\pi(j)+1/2$. This setting ensures that every maximum bounded subsequence beginning with $a\in\{1,\:2,\:\ldots,\:k-1\}$ has length exactly $k+2$. By the following argument, however, the algorithm cannot be sure of this fact unless it sorts $x_1,x_2,\ldots,x_k$.

Suppose that the algorithm cannot infer the order of $x_i$ and $x_j$. Without loss of generality, assume that $i=\pi^{-1}(\pi(j)-1)$, so that $x_i$ immediately precedes $x_j$ in the imagined sorted order of $x_1,x_2,\ldots,x_k$. It is consistent with the algorithm's observations that

$$x_\ell=\begin{cases}\pi(j)+1/2&\text{if }\ell=i\\\pi(\ell)+1/2&\text{if }\ell\ne i,\end{cases}$$

which would give rise to a bounded subsequence of length $k+3>k+2$.

$\endgroup$

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.