September 2008
Visions of Computer Science - BCS International Academic Conference (VOCS)
BCS International Academic Conference
22 - 24 September 2008
esign and analysis of algorithms, Longest increasing subsequence, Data structures, Priority BCS International queue
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.
This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/