Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was going through this dynamic programming problem. However, I have a confusion

enter image description here

enter image description here

enter image description here

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?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.