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?