Upper bounds for the expected length of a longest common subsequence of two binary sequences
Vlado Dančík, Mike Paterson · Random Structures and Algorithms · 1995
Abstract Let f(n) be the expected length of a longest common subsequence of two random binary sequences of length n. It is known that the limit γ = limn→ ∞ n−1 f(n) exists. Improved upper bounds for γ are given using a new method.