Recursive fibonacci using Big Integer time complexity

Question

Could you please explain the complexity of the following algorithm?

public BigInteger fibBigInt() {
    return fibBigInt( 
               BigInteger.valueOf(n), 
               ONE, 
               BigInteger.valueOf(0));
}

private BigInteger fibBigInt(BigInteger start, BigInteger val, BigInteger previous) {
    if (start.compareTo(BigInteger.valueOf(0)) == 0) {
        return previous;
    }
    return fibBigInt( 
               start.subtract(ONE),  
               val.add(previous), 
               val);
}

How does this recursion run in O(n) time? I'm a bit confused.

user_8080648 · Answer

Fibonacci is the standard example of different complexity classes since the naive approach as by definition takes O(2^n) time, where as there is a linear solution which takes only O(n) time. This one works with the linear pattern.

The idea is to have a starting value (fib(0) and fib(1)) and iteratively compute fib(n+2) from fib(n+1) by calling it a single time. The trick is to store not only the result from fib(n+1) but from fib(n) as well. This is done by "rotating" the values for fib(n+1) and fib(n) in each recursion step.

So explaining how this works is best with an example (n=5). Please note that the argument m is the input value which fibonacci number you want. m is decreasing in value and the value 0 marks the end for the recursion. Your code snipped runs with the counter m and has no attribute n.

`n`	`m`	`fib(n+1)`	`fib(n)`	comment
0	5	1	0	first 6 lines of your code
1	4	1+0 = 1	1	iteration step, last 4 lines of your code. The current `fib(n+1)` is the `fib(n+1)`+`fib(n)` from the line above, `fib(n)` is the `fib(n+1)` from the line above.
2	3	1+1 = 2	1	see above
3	2	2+1 = 3	2
4	1	3+2 = 5	3
5	0	5+3 = 8	5	now the term `start.compareTo(BigInteger.valueOf(0))` becomes 0 and therefore the value for `fib(n)` (5) will be returned and "forwarded" back through each recursive call.

This approach is clearly linear and runs therefore in O(n).

Recursive fibonacci using Big Integer time complexity

1 Answers