Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428901 | Information Processing Letters | 2007 | 5 Pages |
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