Talk:Longest increasing subsequence problem
From Wikipedia, the free encyclopedia
[edit] Request
could someone who knows this topic add more on the O(nlgn) solution please
- See the patience sorting if you want one, but beware that it requires TOTAL ordering of the sequence (as opposed to the general graph-style weak ordering). BTW, this article needs to be improved to clearly separate the two cases. --BACbKA 17:51, 12 May 2006 (UTC)
[edit] Dynamic Programming Comment
"Though this is asymptotically equivalent to the longest-common subsequence version of the solution, the constant is lower, as there is less overhead."
Yeah, but I don't think the memory overhead is asymptotically equivalent. If you have confidence that I'm right, please edit in a comment to that effect. 128.113.96.109 18:28, 31 March 2006 (UTC)
you cant use asymptotic analysis and talk about constants.. it makes no sense for the same reason as why we don't consider constants while analysing algorithms in this way.
