<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>

CC BY-SA 4.0
2022-10-10T00:13:36.173Z
Yes, the Smith-Waterman algorithm is often called the Smith-Waterman-Gotoh algorithm for this reason.
user172818
CC BY-SA 4.0
2022-10-21T14:33:29.280Z
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?
Gordon J. Köhn
CC BY-SA 4.0
2022-10-08T22:43:10.083Z
2022-10-08T22:43:10.083Z
Pallie
<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>

<phylogenetics>
Why does the Smith-Waterman algorithm have a complexity of $O(m^2 \times n)$?
# 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?  

---

