# Optimizing the problem

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?

• Have you heard "dynamic programming"? :) – ice1000 Oct 12 '18 at 20:56
• There is a limit for the depth of a recursion defined by the stack size of a program. – kelalaka Oct 12 '18 at 21:07
• 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. – John L. Oct 13 '18 at 1:11
• 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. – ryan Apr 11 '19 at 1:56

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.
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.