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: enter image description here

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.

  • $\begingroup$ Are you interested in the complexity of your DFS memoization solution or just cummulative probability formula? $\endgroup$ – Evil Jan 10 '17 at 0:12
  • $\begingroup$ 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). $\endgroup$ – gnasher729 Jan 10 '17 at 0:40
  • $\begingroup$ @Evil, mainly interested in how I should approach calculating the formula. $\endgroup$ – Dimos Jan 10 '17 at 19:15
  • $\begingroup$ @gnasher729, thanks for the hint. Any specific clue that led you to the conclusion that it's a second degree polynomial ? $\endgroup$ – Dimos Jan 10 '17 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.