Algorithm complexity
To compute the alignment between two sequences we also need to calculate each cell of the matrix :
- Temporal complexity: O(n.m)
In that case, for each cell, we also need to memorise the decision we made during the evaluation of the minimum :
- Spatial complexity : O(n.m)