Answers.Body: <p>I think your source is wrong. You are correct to assume the brunt of its complexity comes from building the <span class="math-container">$m *n$</span> matrix. The main differences are in the calculations per cell and the traceback, but these don't make <span class="math-container">$m ^2$</span>. Wikipedia also gives an identical <span class="math-container">$O(m * n)$</span> as worst case for both algorithms.</p>
  <p>edit:
  Aparently in <a href="https://www.sciencedirect.com/science/article/abs/pii/0022283682903989?via%3Dihub" rel="nofollow noreferrer">this paper</a> the algorithms were improved to go from <span class="math-container">$m^2n$</span> to <span class="math-container">$m*n$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-10T00:13:36.173Z
Answers.Text: Yes, the Smith-Waterman algorithm is often called the Smith-Waterman-Gotoh algorithm for this reason.
Answers.UserDisplayName: user172818
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-21T14:33:29.280Z
Answers.Text: Thank you for the great reference. I gave it a read. So under certain gap penalties, the complexity is reduced. I don't yet fully understand why though. Is there a heuristic explanation?
Answers.UserDisplayName: Gordon J. Köhn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-08T22:43:10.083Z
Answers.LastActivityDate: 2022-10-08T22:43:10.083Z
Answers.UserDisplayName: Pallie
Body: <p>I recently read that original the Smith-Waterman algorithm to do a local pairwise alignment of sequences has a complexity of <span class="math-container">$O(m^2 \times n)$</span>, where <span class="math-container">$m$</span> and <span class="math-container">$n$</span> would be the lengths of the sequences with <span class="math-container">$m$</span> the potentially longer one. What I am wondering is where the additional complexity arises in the algorithm compared to the Needelmann-Wunsch algorithm of global alignment, which has complexity <span class="math-container">$O(m \times n)$</span>.</p>
  <p>Am I correct to assume the <span class="math-container">$m\times n$</span> for the Needelmann-Wunsch algorithm comes from building up the scoring matrix - whereas the traceback is negligible in complexity i.e. <span class="math-container">$O(m\times n + m)$</span>? Hence we arrive at <span class="math-container">$O(m\times n)$</span>.</p>
  <p>Why is there a <span class="math-container">$m^2$</span> term for the Smith-Watermann algorithm?</p>
  
Tags: <phylogenetics>
Title: Why does the Smith-Waterman algorithm have a complexity of $O(m^2 \times n)$?
ThreadText: # Why does the Smith-Waterman algorithm have a complexity of $O(m^2 \times n)$?
  
  (Asked by: username_0 on 2022-10-08)
  
  I recently read that original the Smith-Waterman algorithm to do a local pairwise alignment of sequences has a complexity of $O(m^2 \times n)$, where $m$ and $n$ would be the lengths of the sequences with $m$ the potentially longer one. What I am wondering is where the additional complexity arises in the algorithm compared to the Needelmann-Wunsch algorithm of global alignment, which has complexity $O(m \times n)$.
  
  Am I correct to assume the $m\times n$ for the Needelmann-Wunsch algorithm comes from building up the scoring matrix - whereas the traceback is negligible in complexity i.e. $O(m\times n + m)$? Hence we arrive at $O(m\times n)$.
  
  Why is there a $m^2$ term for the Smith-Watermann algorithm?
  
  **Tags:** phylogenetics
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-08. Score: 2
  
  I think your source is wrong. You are correct to assume the brunt of its complexity comes from building the $m \*n$ matrix. The main differences are in the calculations per cell and the traceback, but these don't make $m ^2$. Wikipedia also gives an identical $O(m \* n)$ as worst case for both algorithms.
  
  edit:
  Aparently in [this paper](https://www.sciencedirect.com/science/article/abs/pii/0022283682903989?via%3Dihub) the algorithms were improved to go from $m^2n$ to $m\*n$
  
  > **Comments:**
  > **username_2**: Yes, the Smith-Waterman algorithm is often called the Smith-Waterman-Gotoh algorithm for this reason.  
  > **username_0**: Thank you for the great reference. I gave it a read. So under certain gap penalties, the complexity is reduced. I don't yet fully understand why though. Is there a heuristic explanation?  
  
  ---
  
  