Editing Needleman–Wunsch algorithm (section)

== Complexity ==
Computing the score <math>F_{ij}</math> for each cell in the table is an <math>O(1)</math> operation. Thus the time complexity of the algorithm for two sequences of length <math>n</math> and <math>m</math> is <math>O(mn)</math>.<ref name=":0">{{Cite book|title=Algorithms in bioinformatics : a practical introduction|last=Wing-Kin.|first=Sung|date=2010|publisher=Chapman & Hall/CRC Press|isbn=9781420070330|location=Boca Raton|pages=34–35|oclc=429634761}}</ref> It has been shown that it is possible to improve the running time to <math>O(mn/ \log n)</math> using the [[Method of Four Russians]].<ref name=":0" /><ref>{{Cite journal|last1=Masek|first1=William|last2=Paterson|first2=Michael|date=February 1980|title=A faster algorithm computing string edit distances|journal=Journal of Computer and System Sciences|volume=20|pages=18–31|doi=10.1016/0022-0000(80)90002-1|doi-access=free|hdl=1721.1/148933|hdl-access=free}}</ref> Since the algorithm fills an <math>n \times m</math> table the space complexity is <math>O(mn).</math><ref name=":0" />