Return to Answer

The time-complexity of dynamic-programming with memoization

Here is the simple principle. Suppose an algorithm

• applies dynamic programming to solve a problem,
• with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
• where each subproblem is computed only once thanks to memoization,
• and it takes $O(u)$ time for some expression $u$ to compute each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,

then the time-complexity of the algorithm is $O(su)$, in general.

Analysis of the algorithm in the question

Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp. (They represent $O(mn)$ subproblems.)

  The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.

How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 be executed? Except the very first time that is triggered by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, triggered by the execution of the code block mentioned above. So line 4, 5 and 6 are executed at most $1 + 4(m+1)(n+1)$ times.

So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for line 1 and 2. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.

The analysis above serves as an example to illustrate and validate the principle.

Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to compute each subproblem, ignoring the time for the recursive calls to obtain results of other subproblem. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.

The time-complexity of dynamic-programming with memoization

Here is the simple principle. Suppose an algorithm

• applies dynamic programming to solve a problem,
• with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
• where each subproblem is computed/solved only once thanks to memoization,
• and it takes $O(u)$ time for some expression $u$ to compute/solve each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,

then the time-complexity of the algorithm is $O(su)$, in general.

Analysis of the algorithm in the question

Let us estimate how many line-executions are done if the algorithm is run upon an input of a string of length $m$ and a pattern of length $n$.

There are $(m+1)(n+1)$ entries in the table dp  (which represent $O(mn)$ subproblems). The code that actually computes and updates the entries are the code block from line $7$ to line $17$. Because of memoization, these lines will be executed at most once for each entry. So these $17-7+1$ lines will be executed at most $(m+1)(n+1)$ times, i.e., these lines correspond to at most $(17-7+1)(m+1)(n+1)$ line-executions.

How many times will line $4$ (for building and quitting calling stack frames), line $5$ and $6$ be executed? Except the first time that is triggered by line $2$, the execution of them is triggered by the execution of any one of $4$ lines, line $9$, $10$, $12$, or $15$, which happens during the execution of the code block mentioned above. So line $4$, $5$ and $6$ are executed at most $1 + 4(m+1)(n+1)$ times, i.e., these $3$ lines correspond to at most $3(1 + 4(m+1)(n+1))$ line-executions.

So, the total number of line-executions is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for the one-time execution of line $1$ and $2$ at the start of running the algorithm. We can check that it takes $O(1)$ time to execute each line, except for possibly line $2$, which is executed once that costs up to $O(mn)$ time. Hence, the time-complexity of the algorithm is $O(mn)$.

The analysis above serves as an example to illustrate and validate the principle.

Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to solve each subproblem, considering all recursive calls as taking $O(1)$ time. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$. 

Thanks to memoization, it is easy to obtain an upper bound for the worst-case time-complexity that is usually good enough for an algorithm that applies dynamic programming by tabulation.

Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp.

The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.

How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 be executed? Except the very first time that is trigger by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, trigger by the execution of the code block mentioned above. So line 5 and line 6 are executed at most $1 + 4(m+1)(n+1)$ times.

So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 2(1 + 4(m+1)(n+1)) + 3,$$ where the last number $3$ is for the first 3 line. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.

If we let $n$ stand for the total input length instead, the time-complexity is $O(n^2)$.

The time-complexity of dynamic-programming with memoization

Here is the simple principle. Suppose an algorithm

• applies dynamic programming to solve a problem,
• with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
• where each subproblem is computed only once thanks to memoization,
• and it takes $O(u)$ time for some expression $u$ to compute each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,

then the time-complexity of the algorithm is $O(su)$, in general.

Analysis of the algorithm in the question

Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp. (They represent $O(mn)$ subproblems.)

The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.

How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 be executed? Except the very first time that is triggered by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, triggered by the execution of the code block mentioned above. So line 4, 5 and 6 are executed at most $1 + 4(m+1)(n+1)$ times.

So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for line 1 and 2. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.

The analysis above serves as an example to illustrate and validate the principle.

Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to compute each subproblem, ignoring the time for the recursive calls to obtain results of other subproblem. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.

Thanks to memoization, it is easy to obtain an upper bound for the worst-case time-complexity that is usually good enough for an algorithm that applies dynamic programming by tabulation.

Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp.

The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.

How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 will be executed? Except that very first time that is trigger by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, trigger by the execution of the code block mentioned above. So line 5 and line 6 are executed at most $4(m+1)(n+1)$ times.

So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 2\cdot4(m+1)(n+1)+ 3$$, where the last $3$ is for the first 3 line. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.

If we let $n$ stand for the total input length instead, the time-complexity is $O(n^2)$.

Thanks to memoization, it is easy to obtain an upper bound for the worst-case time-complexity that is usually good enough for an algorithm that applies dynamic programming by tabulation.

Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp.

The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.

How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 be executed? Except the very first time that is trigger by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, trigger by the execution of the code block mentioned above. So line 5 and line 6 are executed at most $1 + 4(m+1)(n+1)$ times.

So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 2(1 + 4(m+1)(n+1)) + 3,$$ where the last number $3$ is for the first 3 line. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.

If we let $n$ stand for the total input length instead, the time-complexity is $O(n^2)$.