0
$\begingroup$

What is the optimal time complexity for an algorithm that solves the Longest Increasing Subsequence problem?

I am aware of the O(n log n) algorithm mentioned in textbooks (and on the Wikipedia article). Can we do better? Is it possible to solve this problem in O(n) time?

Improve this question
$\endgroup$
2
  • $\begingroup$ "Tight Ω(n lg n) lower bound for finding a longest increasing subsequence" (which I don't have access to) claims that the answer is No. But you can get sublinear time if you only want to estimate the length: "Estimating the Longest Increasing Subsequence in Nearly Optimal Time". $\endgroup$
    – Dmitry
    Feb 15 at 6:23
  • $\begingroup$ The $\Omega(n\log n)$ lower bound is in the decision tree model and its extensions. In particular, it doesn't apply when the alphabet is fixed. $\endgroup$
    – Yuval Filmus
    Feb 16 at 6:28

0

Reset to default

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.

Browse other questions tagged or ask your own question.