Analysis of Time and Space Efficiency

The optimal global alignments can be obtained using dynamic programming in 0 mn) time. When m = n, the time taken becomes 0(n ). 

Proof The (m+l)(n+l) table needs to be filled. Each and every entry is computed with a maximum of 6 table look-ups, 3 additions, and a 3-way maximum in time c. Complexity of the algorithm = c( +l)(m+l) = 0(mn). 

Reconstructing a single alignment = 0(n+m) time. The space required for retaining the grades of alignment in the table is (mti) also. 

---