Runtime Complexity of 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)$.