1
$\begingroup$

I have a recurrence relation:

$$f(a,b) = \begin{cases} 1 & (a,b) = (0, 0)\\ 1 & (a,b) = (a, 0)\\ 0 & (a,b) = (0, b)\\ 2a & (a,b) = (a,1)\\ f(a-1,b) + f(a-2, b-1) + f(a-1,b-1) & \mathrm{otherwise} \end{cases}$$

Where the constraints: $1 \leq a \leq 10^9$ and $1 \leq b \leq 1000$. I tried using recursion to find out the values but the time complexity was very high. I also tried using a dp table but that has a high time complexity as well. Also, since a can be upto $10^9$, it isn't possible to create such a large table as the space complexity will be too high and I'll get a runtime error. I want to optimize this code so that its time complexity gets reduced. Can anyone help me to achieve this? I mean which data structure to use or what algorithm should I implement to achieve this?

$\endgroup$
  • $\begingroup$ Have you heard "dynamic programming"? :) $\endgroup$ – ice1000 Oct 12 '18 at 20:56
  • $\begingroup$ There is a limit for the depth of a recursion defined by the stack size of a program. $\endgroup$ – kelalaka Oct 12 '18 at 21:07
  • 1
    $\begingroup$ Welcome to Computer Science! If this problem comes from an online source such as a programming contest or a coding camp, please provide a URL. If it comes from a book or a paper, a reference. All those information motivate and help people answer the question faster and better. For me, it is not clear what to compute. Do you need to output all values of f(a,b) for 1<=a<=10^9 and 1<=b<=1000 at once? Please add those information in the question since people and search engine are not expected to look at comments. $\endgroup$ – John L. Oct 13 '18 at 1:11
  • 1
    $\begingroup$ This can be done in logarithmic time if you use state matrices (see more info here). I'll see if I can think of one for this recurrence. Also see here. $\endgroup$ – ryan Apr 11 '19 at 1:56
0
$\begingroup$

you can go to Dynamic programming. To achieve benefits do this you need overlapping recursion.

Easiest way yo program it, using a Map library as Memoization. Store any value calculated. Check any value from the map before calculation. This will eliminate the recalculations.

The simple case is always the Fibonacci Sequence, in which given $n$ find the $F(n) = F(n-1) + F(n-2)$.

You could see the overlappings easily. Make an array to store $F_i$ once found to prevent refound, Top-Down.

Buttom up; Start from the lowest of the recursion to reach the target.

For your case you need a table of size $10^9 \times 1000$ to fill. If the size is big, you may reuse some rows.

$\endgroup$

Your Answer

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

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