Editing Longest common subsequence (section)

== Complexity ==
For the general case of an arbitrary number of input sequences, the problem is [[NP-hard]].<ref>{{cite journal| author = David Maier| title = The Complexity of Some Problems on Subsequences and Supersequences| journal = J. ACM| volume = 25| year = 1978| pages = 322&ndash;336| doi = 10.1145/322063.322075| publisher = ACM Press| issue = 2| s2cid = 16120634| doi-access = free}}</ref> When the number of sequences is constant, the problem is solvable in polynomial time by [[dynamic programming]].

Given <math>N</math> sequences of lengths <math>n_1, ..., n_N</math>, a naive search would test each of the <math>2^{n_1}</math> subsequences of the first sequence to determine whether they are also subsequences of the remaining sequences; each subsequence may be tested in time linear in the lengths of the remaining sequences, so the time for this algorithm would be
:<math>O\left( 2^{n_1} \sum_{i>1} n_i\right).</math>

For the case of two sequences of ''n'' and ''m'' elements, the running time of the dynamic programming approach is [[Big O notation|O]](''n'' × ''m'').<ref>{{cite journal |last1=Wagner |first1=Robert |last2=Fischer |first2=Michael |date=January 1974 |title=The string-to-string correction problem |journal=[[Journal of the ACM]] |volume=21 |issue=1 |pages=168–173 |doi=10.1145/321796.321811 |citeseerx=10.1.1.367.5281 |s2cid=13381535 }}</ref> For an arbitrary number of input sequences, the dynamic programming approach gives a solution in

:<math>O\left(N \prod_{i=1}^{N} n_i\right).</math>

There exist methods with lower complexity,<ref name="BHR00">
{{cite conference | author = L. Bergroth and H. Hakonen and T. Raita | conference = Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000 | title = A survey of longest common subsequence algorithms | date =7–29 September 2000 |location=A Curuna, Spain | isbn = 0-7695-0746-8 | pages = 39&ndash;48 | doi = 10.1109/SPIRE.2000.878178 | publisher = IEEE Computer Society| s2cid = 10375334 }}</ref>
which often depend on the length of the LCS, the size of the alphabet, or both.

The LCS is not necessarily unique; in the worst case, the number of common subsequences is exponential in the lengths of the inputs, so the algorithmic complexity must be at least exponential.<ref>{{cite arXiv | author = Ronald I. Greenberg | title = Bounds on the Number of Longest Common Subsequences  | date = 2003-08-06  | eprint = cs.DM/0301030}}</ref>