Time Complexity of Memoized Solution I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on an array $A_1,\ldots,A_n$, where:

$i$ is the starting index
$2m$ is the maximum size of the window at $i$

Here is the recurrence:
$$
u(i,m) =
\begin{cases}
\sum\limits_{j=i}^{n} A_j &amp; \text{if } i + 2m-1 &gt; n, \\
\sum\limits_{j=i}^{n} A_j - \min\limits_{\substack{0 \leq k \leq 2m-1 \\ i+k \le n}} u(i+k+1, \max(m,k+1)),
&amp; \text{if } i + 2m-1 \le n.
\end{cases}
$$
(Using $O(n)$ preprocessing, the sums can be computed in $O(1)$.)
I am interested in the value of $u(1,1)$.
However, I am not sure about the time complexity of this solution.
According to me :

There are $m \times n$, where:

$n$ is the number of elements in $A$.
$m$ is the width of window that varies at each step.


Each state is being calculated only once.
$m$ can not be greater than $n$, the size of $A$.

Hence, the time complexity of the solution should be $O(n^2)$.
Is there something that I am missing? Is there a mathematical way to prove this?
For each $i,m$ in the range $n/3 \leq i,m \leq 2n/3$, computing the recurrence requires going over $\Theta(n)$ values of the parameter $k$, hence calculating $u(i,m)$ for all of these values of $i,m$ requires time $\Theta(n^3)$.
Do you actually encounter such values of $i,m$ when calculating $u(1,1)$? It's not immediately clear to me, but you'll have to rule it out if you want to prove a better upper bound on the running time of your procedure.