Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)
Maxime Crochemore, Ely Porat · Electronic workshops in computing · 2008
We consider the complexity of computing a longest increasing subsequence parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, . . . , n } can be computed in time O ( n log log k ) in the RAM model, improving the previous 30-year bound of O ( n log log n ). The optimality of the new bound is an open question.