reduce Big-O recursive algorithm to linear

Question

I came across the following problem:

F(n)= 0 when n = 0;
F(n)= 1 when n = 1;
F(n)= F(n-1) + F(n-2) when n>1;

I can already solve this recursively like this:

int F(int n) {
    if(n=0) return 0;
    if(n=1) return 1;
    if(n>1) return F(n-1) + F(n-2);
}

but the complexity is O(n^2). How can this be solved with the complexity O(n)?

What book should I need to read to solve a problem like this?

"Dynamic Programming" is the name for the solution to this puzzle. — Mooing Duck, Dec 02 '17 at 01:15
*Memoization* is another technique that you should read about. See [What is the difference between memoization and dynamic programming?](https://stackoverflow.com/q/6184869/643383). — Caleb, Dec 02 '17 at 08:01

score 1 · Answer 1 · answered Dec 02 '17 at 07:29

This function is exactly what you are looking for. And yes, this is Dynamic Programming.

static ArrayList<Double> getSeries(int n)
{
    ArrayList<Double> series = new ArrayList<>();
    series.add(0.0); // This is working as replacement of the F(0)
    series.add(1.0); // This is working as replacement of the F(1)
    double x, y;

    for (int i = 1; i < n; i++)
    {
        x= series.get(i - 1); // This is working as replacement of the F(n-2)
        y = series.get(i); // This is working as replacement of the F(n-1)
        series.add(x + y);
    }

    return series;
}

Try this code here:- https://ideone.com/IMixm9

The basic trade-off of computational space and time can be seen here.

Before

Space Complexity :- log 
Time Complexity  :- 2^n

Now

Space Complexity :- n
Time Complexity  :- n

reduce Big-O recursive algorithm to linear

1 Answers1