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

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.

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)}

where {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} is the golden ratio and {\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}} is its conjugate.

2 Likes

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