3 The length of the refinement path to search is at most N + M (all deletions/insertions), so refining the path requires at most (N + M )w comparisons.
the full N M comparisons can be approximated by (N + M )w + N 2 M 2 comparisons.