|
I was going through this dynamic programming problem. However, I have a confusion
In the third picture, having the black border, I didn't get how the For each, we try each string of the k strings B ∈ L, and compute the optimal alignment of B with A[t : j] in time O(n(j − t)) = O(mn). How it was O(n(j-t)). Also, I didn't get how come there are $O(m^2)$ values of c(t,j) Can anyone please explain? |
||||
|
|
|
The man idea is that they're trying to build a table containing all possible pairs of $t$ and $j$. After this is done, they can find an optimal solution from the table. We know that $t$ and $j$ are both between 1 and $m$, so there are at most $m$ values for $t$ and at most $m$ values for $j$. In other words, there are at most $O(m)$ values for $t$ and $O(m)$ values for $j$ for a total of $O(m) \cdot O(m)$ combinations of $t$ and $j$, or $O(m^2)$. As the table is built, we can consider a particular $j$ and $t$. There are $j-t$ values between $t$ and $j$, so this gives a size of $j-t$ or $O(j-t)$. This takes time $O(n)$ for each value, so we multiply $O(n)$ by $O(j-t)$ to get $O(n(j-t))$. I hope this helps to explain things. You may also want to consider posting this at Stack Exchange's Computer Science Beta. Just remember to wait a little while before posting there, as cross-posting is frowned on. Let us know if you'd like more explanation. |
|||
|
|
