Fibonacci Numbers in Java - `O(n)` time and `O(1)` space complexity and without using Recursion

Processing Coding Questions
1

  1. How can I get the N-th Fibonacci number with O(n) time and O(1) space complexity.

  2. How to calculate Fibonacci numbers without Recursion or Iteration?

This is the code that I took from here, using Recursion with Memoization in Java

import java.util.*;
public class fibonacci{
    public static int fibo(int n){
        if(n==1)return values[0];
        if(n==2)return values[1];
        else{
            values[n-1]=fibo(n-1)+fibo(n-2);
            return values[n-1];
        }
    }
    public static void main(String args[]){
        int n;
        Scanner sc= new Scanner(System.in);
        n=sc.nextInt();
        sc.close();
        values[0]=0;
        values[1]=1;
        System.out.println(fibo(n));
    }
    static int values[]=new int[1000];
}

The question is how can I implement the same without using Recursion.

2

Can you please merge your 2 threads?

3

There is a formula to instantly calculate the nth fibonacci number.
Wikipedia says:
The partial fraction decomposition is given by

{\displaystyle s(x)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi x}}-{\frac {1}{1-\psi x}}\right)}

{isplaystyle s(x)={rac {1}{qrt {5}}}eft({rac {1}{1-arphi x}}-{rac {1}{1-si x}}ight)}|0x0

where {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}arphi ={rac {1+{qrt {5}}}{2}}|0x0 is the golden ratio and {\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}}{isplaystyle si ={rac {1-{qrt {5}}}{2}}}|0x0 is its conjugate.

2 Likes
4

See Wolfram MathWorld: Binet’s Fibonacci Number Formula.

Since we can only store approximations of φ and ψ, calculations of the nth Fibonacci number using Binet’s formula can be expected to diverge from the truth for high values of n.

Let’s test this using Python 3 …

def fib_binet(n):
    # Binet's method (approximation) O(1)
    phi = (5.0 ** 0.5 + 1.0) / 2.0
    psi = 1.0 - phi
    return int((phi ** n - psi ** n) / (phi - psi))

def fib_iter(n):
    # iterative method (exact) O(n)
    a, b = 0, 1
    for i in range(n):
        a, b = a + b, a
    return a

for n in range(80):
  if fib_binet(n) != fib_iter(n):
    print(n - 1, fib_binet(n - 1), fib_iter(n - 1))
    print(n, fib_binet(n), fib_iter(n))
    break

Output:

71 308061521170129 308061521170129
72 498454011879265 498454011879264

Calculations were fine for values of n between 0 and 71, inclusive, but diverged from the truth, thereafter.

Please feel free to try this with Java, and post the results here.

1 Like