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
(
n
3
/
2
log
n
)
and storage requirement
O
(
n
)
. It is proved that the expected length
μ
(
n
)
of the LICS satisfies
lim
n
→
∞
μ
(
n
)
2
n
=
1
. Numerical experiments with the algorithm suggest that
|
μ
(
n
)
−
2
n
|
=
O
(
n
1
/
6
)
.