1
$\begingroup$

I am struggling to analyze the runtime complexity of the following algorithm formally:

Given a string s and a dictionary of words dict(wordDict), add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

The proposed algorithm:

    wordBreak(s, wordDict) {
        res; //a container used to store the final result.
        if(the length of s is zero or s is invalid) {
            just output res directly.
        }
        if(we have already encountered s before) {
            return the res that s corresponds to.
        }
        if(wordDict contains s) {
            add s to res.
        }
        (looping index from 0 to the length of s) {
            t = the substring of s starting from index to the end of s
            if(wordDict contains t) {
                temp = wordBreak(substring of s from 0 to index , wordDict);
                if(temp is not empty) {
                    (looping index j from 0 to the length of temp) {
                        cancatenate the jth element of temp with t and add it to res.
                    }
                }
            }
        }
        store the result of s to storage.
        return res;
    }
}

My analysis:

Giving the algorithm, denote the length of $s$ by n. Suppose the runtime complexity is $T(n)$, then we would have something like $T(n) = T(n - 1) + T(n - 2) + \ldots + T(0) + n + 2^{n-1} - 1$, where I add $n$ because we are looping through $s$. In the meantime we are looping through temp which is a list of results. In the worst case temp can contain $2^{n-1} - 1$ results(subdivisions coming from a string of length $n - 1$). However this does not take into consideration the effect of memoization and I do not know how to achieve that. Specifically my question are:

  1. What is the correct time complexity analysis? My guess is that it is at least $n 2^{n-1}$ which is the time taken to create the result list but this is a wild guess without formal proof.

  2. How does the analysis differ from the case where there is no memoization.

$\endgroup$
5
  • 1
    $\begingroup$ You're analyzing the complexity without memoization. With memoization, you need to count each subproblem only once. $\endgroup$ – Yuval Filmus Dec 12 '20 at 22:03
  • $\begingroup$ And that's exactly the point of memoization. You remember solutions to sub problems, and if the same sub problem comes up again, you don't need to solve it again because you remembered the solution. $\endgroup$ – gnasher729 Dec 13 '20 at 0:11
  • $\begingroup$ How do you account for memoization formally? I have no idea hot to carry out the anaylsis. $\endgroup$ – penny Dec 13 '20 at 1:59
  • $\begingroup$ Anything you have calculated before can be calculated again in the time it takes to look up the state. This is often O(1). $\endgroup$ – gnasher729 Dec 13 '20 at 14:41
  • $\begingroup$ Take a large sheet of paper and calculate fib(50) with pen and paper, where fib(n) = 1 if n ≤ 1, and fib(n) = fib(n-1) + fib(n-2) otherwise. $\endgroup$ – gnasher729 Dec 13 '20 at 14:55
1
$\begingroup$

Memoization is related to dynamic programming in the following way.

Let $V$ be the set of all possible inputs to the function $f$. Draw an edge from $x \in V$ to $y \in V$ if the computation of $f(x)$ invokes $f(y)$. The resulting graph is a directed acyclic graph (DAG).

Now suppose that you want to compute $f(x)$. Let $V(x)$ be the set of all vertices reachable from $V(x)$. In dynamic programming, we arrange $V(x)$ in reverse topological order, and compute $f$ in that order.

As an example, consider the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$, with base cases $F(1) = 1$ and $F(0) = 0$. In this case $V$ consists of all natural numbers, the edges are $n\to n-1$ and $n \to n-2$ (for all $n \geq 2$), $V(n) = \{0,\ldots,n\}$, and reverse topological order is $0,\ldots,n$. That is, we compute $F(0),F(1),F(2),\ldots,F(n)$ in this order. Whenever compute $F(m)$, all other values of $F$ which are needed are already available.


How do we compute the complexity of a memoized function? We imagine that instead of implementing it in a recursive fashion, we use dynamic programming. This means that each recursive call now takes $O(1)$; but when running $f(x)$, we actually evaluate $f$ on all inputs in $V(x)$.


In your case, $V(x)$ consists of all prefixes of $x$. In order to evaluate the running time, you need to compute, for each $n$, the running time of your procedure $T(n)$ on inputs of length $n$, assuming that all recursive calls are $O(1)$. The final answer is then $T(0) + \cdots + T(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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