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?

  • $\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, 2023 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$ Feb 16, 2023 at 6:28


Your Answer

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

Browse other questions tagged or ask your own question.