# Why does the Smith-Waterman algorithm have a complexity of $O(m^2 \times n)$?

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?

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 the algorithms were improved to go from $$m^2n$$ to $$m*n$$