1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I am not sure that anyone is going to want to read your entier code and analyze its time complexity. Rather than asking someone to do this entire project for you, I suggest you learn about the general techniques (if there's some technique you don't know, you can ask about that concept), try doing it yourself, and if there is some place where you are stuck, ask about that specific aspect. It sounds like you've already answered your own question, so I'm not sure what more there is to say. We prefer concise pseudocode over actual code. Not everyone here reads C++. $\endgroup$
    – D.W. ♦
    Apr 7, 2021 at 19:05
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Apr 7, 2021 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Apr 8, 2021 at 7:21

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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