Algorithm complexity
To compute the distance between two sequences we need to calculate each cell of the matrix :
- Temporal complexity: O(n.m)
To compute the value of a cell, we only need the left, top and diagonal values. So, we only need to memorise the equivalent of a row of the matrix :
- Spatial complexity : O(n)