Problem Detail: 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}{argmax} ; # {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.
Asked By : Tavian Barnes
Answered By : David Eisenstat
No, $Omega(nlog 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 $ain{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 $ain{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=ipi(ell)+1/2&text{if }ellne i,end{cases}$$ which would give rise to a bounded subsequence of length $k+3>k+2$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30576 3.2K people like this
