Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?
-
29-09-2020 - |
Question
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?
Solution
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.