Reduce the space complexity of the following fibonacci algorithm

Question

Reduce the space complexity of the following fibonacci algorithm.

I need help with this. I can't think of any way to do this. Any help would be much appreciated.

public static long fibonacci (int n){
    long[] f = new long[n+1];
    f[0] = 0;
    f[1] = 1;
    for(int i = 2; i <=n; i++)
      f[i] = f[i-1] + f[1-2];
    return f[n];
}

Answer 1

Basically, the problem is this line:

long[] f=new long[n+1];

This line creates a long array requiring n+1 longs what requires the space complexity to be linear.

A recursive approach as @tzortzik mentioned would have the same space complexity as every stack frame requires space and you would also require n-1 stack frames.

The key in your case is that you do not need the array. You always just need two values.

After all, there is no reason for saving the previous calculations if you don't use them.

public static long fibonacci(int n){
    long last=0;
    long current=1;
    for(int i=1;i<n;i++){
        long tmp=current;
        current+=last;
        last=current;
    }
}

This is basically the same as your algorithm but without the array.

Instead of setting [i] to the sum of [i-2] and [i-1] of an array, it sets current to the sum of last and current. Instead of going on with the array, it sets last to the previoud value of current (backed up by tmp).

It would also be possible to eliminate the temporary variable using the knowledge that you just added last to current and you can get the value back by substracting it again.

public static long fibonacci(int n){
    long last=0;
    long current=1;
    for(int i=1;i<n;i++){
        current+=last;
        last=current-last;
    }
}

This would not change the complexity and in reality, this would also not change much.