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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

Your Answer


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.