Runtime Complexity of Memoization 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 = &quot;catsanddog&quot;, dict = [&quot;cat&quot;, &quot;cats&quot;, &quot;and&quot;,
&quot;sand&quot;, &quot;dog&quot;].
A solution is [&quot;cats and dog&quot;, &quot;cat sand dog&quot;].

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:

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.

How does the analysis differ from the case where there is no memoization.
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)$.