# Complexity of exponential algorithm, optimised with memoization?

I was solving a problem, where one part of it was the following:

"Given a m-sided dice ([1,m] values) that will be rolled n times, calculate the possibility that the total sum of rolls will be higher than b"

Initially, I implemented a naive exponential solution, discovering the whole state space (DFS-like). Then, I realised that this algorithm repeats the calculation for a given number of remaining rolls and current sum. So, I optimised it, saving these calculations and using them later. For example, let's say we have a 4-sided dice that will be rolled 2 times (m=4, n=2). The below image shows the state space:

With green color are the values that were cached from previous computations and will be returned directly from memory. With red color are the values that will be normally computed. I have been trying to calculate the complexity of the algorithm:

• The initial algorithm, where there is no "caching" of values, has obviously an exponential complexity of O(M^n)
• The iterations needed for the optimised algorithm follow the below pattern:

For (m=4,n=2): 11 = 4 + 7 = 4 + [(4*2)-1]

For (m=4,n=3): 21 = 4 + 7 + 10 = 4 + [(4*2)-1] + [(4*3)-2]

For (m=4,n=4): 34 = 4 + 7 + 10 + 13 = 4 + [(4*2)-1] + [(4*3)-2] + [(4*4)-3]

...

This seems to be a mathematical sequence, but I can't calculate the exact formula. Any help much appreciated.

• Are you interested in the complexity of your DFS memoization solution or just cummulative probability formula? – Evil Jan 10 '17 at 0:12
• Hint: It is a second degree polynomial in n, an^2 + bn + c. You determine a, b, c from the values for n = 2, 3 and 4 (or 1, 2, 3 if you prefer). – gnasher729 Jan 10 '17 at 0:40
• @Evil, mainly interested in how I should approach calculating the formula. – Dimos Jan 10 '17 at 19:15
• @gnasher729, thanks for the hint. Any specific clue that led you to the conclusion that it's a second degree polynomial ? – Dimos Jan 10 '17 at 19:16