# 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 & \text{if } i + 2m-1 > 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)), & \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?

• General techniques for analyzing running time can be found here: cs.stackexchange.com/q/23593/755. Note that you've given an upper bound on the running time. $O(n^2)$ is an upper bound. If you want to prove that this is the best upper bound, your next step would be to find some input that causes this to take $\Omega(n^2)$ time.
• Hope I translated your code to a recurrence correctly. It does seem like you might have some mistakes in your code (for example the strange condition $i+k \leq n$). Also, for some reason you computed the sum in the first case explicitly instead of using the running sum trick that you use in the second case. Apr 8, 2021 at 7:21
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.