# Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red card drawn, we get 1 dollar and lose 1 dollar for every black card drawn. The problem consists in finding an algorithm which returns the expected value of the game. If we denote by $b$ and $r$, respectively, the number of black and red cards left in the deck at any time, the expected value of the game $E(b,r)$ satisfies:

$$E(b,r)=\max\left\{b-r,\frac{b}{b+r}\,E(b-1,r)+\frac{r}{b+r}\,E(b,r-1)\right\}\,,$$

with boundary conditions $E(0,r)=0$ and $E(b,0)=b$. The expected value of the game is therefore given by $E(26,26)$.

My question is, if we implement the recursive algorithm associated with the above formula, how can we determine its complexity? Using the trivial cases of $E(1,1)$ and $E(2,2)$, it would appear that we are dealing with exponential complexity, but is there a way to prove this properly, and if so, what is the number of necessary operations to compute $E(n,n)$ for an arbitrarily large integer $n$? Any ideas or references to literature would be greatly appreciated.

• Is "For every red ... black card drawn." when the red card is drawn or when we ask him to stop? ​ ​ – user12859 Feb 4 '16 at 5:43
• Hint: use memoization. – Raphael Feb 4 '16 at 7:48
• Your recurrence is wrong. Even your boundary conditions are wrong (switch black and red). Start with fixing your recurrence. – Yuval Filmus Feb 4 '16 at 8:27
• The answer I get is 41984711742427/15997372030584. – Yuval Filmus Feb 4 '16 at 8:28
• @G.Bach When there's only black left you want to stop, so $E(b,0) = 0$. When there's only red left you want to take all of them, so $E(0,r) = r$. I am measuring payoff; what are you measuring? – Yuval Filmus Feb 4 '16 at 9:15

As pointed out in the comments, your recurrence is wrong (though equivalent for $b=r$; it's a recurrence for $E(b,r)+b-r$). Also, you can solve this efficiently using memoization or its more principled cousin, dynamic programming. The dynamic programming solution calculates iteratively $E(i,j)$ for $i+j=0,1,\ldots,52$.
Finally, to answer your question, if you implement you original solution, you get a running time satisfying the recurrence $$T(b,r) = C + T(b-1,r) + T(b,r-1),$$ with initial conditions $T(b,0) = O(1)$, $T(0,r) = O(1)$. If $T'(b,r) = T(b,r)-C$ then $$T'(b,r) = T'(b-1,r) + T'(b,r-1),$$ a recurrence solved by $\alpha \binom{b+r}{r}$. Taking the initial conditions into account, we get that $$T(b,r) = \Theta\left(\binom{b+r}{r}\right).$$ In particular, $$T(n,n) = \Theta\left(\binom{2n}{n}\right) = \Theta\left(\frac{4^n}{\sqrt{n}}\right).$$ (This assumes all arithmetic is $O(1)$. The running time is actually somewhat larger since the relevant numbers grow fast, but this is a (multiplicative) lower-order factor.)
• @user223935 I made the same thinko, but that's not how to go about this. $E(b,r)$ is independent of the values $E(b+c, r+d)$ for any $c,d>0$, or in words: the expected payoff for the remaining(!) game doesn't change, whether you already played a couple of rounds before it or not. At every step, you just optimize the expected payoff of the remaining game, not the overall game. That's why Yuval correctly says $E(0,r) = r$ and $E(b,0) = 0$ in a comment to your question. – G. Bach Feb 4 '16 at 14:49
• @YuvalFilmus Having a second look, $E(b,r) + b - r$ is right. – G. Bach Feb 4 '16 at 15:35