Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time?

For example, let's say that $A = [4, 11, 6, 2, 9, 7]$. Then, one of the required sequences can be $[2, 7, 11]$, which is the sorted version of the subsequence $[11, 2, 7]$. Your strategy can give any such subsequence in a sorted order.

Yes, I think that it's 99.99% impossible. But, I don't know for sure. Can anyone show that there cannot exist such a strategy or prove otherwise?


1 Answer 1


It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time.

Consider the following sorting algorithm:

def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

In result, the running time is $O(n + \frac n2 + \frac n4 + ...) = O(n)$, which violates a well-known lower bound for sorting.

  • $\begingroup$ By b = a.exclude(b), do you mean b = a.exclude(subseq)? $\endgroup$
    – Hong Jiang
    Jul 16, 2020 at 7:04
  • $\begingroup$ @HongJiang, thanks, fixed $\endgroup$
    – user114966
    Jul 16, 2020 at 7:11
  • $\begingroup$ So it seems at least O (n log n) is needed in the worst case to find the subsequence. $\endgroup$
    – gnasher729
    Jul 16, 2020 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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