Article ID Journal Published Year Pages File Type
428901 Information Processing Letters 2007 5 Pages PDF
Abstract

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics