Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

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?

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.

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