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

**URL:** <https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694>\
**Category:** Coding Questions\
**Created:** [October 8, 2021, 12:58pm UTC](https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694 "2021-10-08T12:58:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![panahur](https://avatars.discourse-cdn.com/v4/letter/p/258eb7/32.png) [@panahur](https://discourse.processing.org/u/panahur)\
**Post date:** [October 8, 2021, 12:58pm UTC](https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694/1 "2021-10-08T12:58:18Z")

</div>

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](https://www.scaler.com/topics/fibonacci-series-in-java/), using Recursion with Memoization in Java

```auto
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.

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [October 8, 2021, 4:14pm UTC](https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694/2 "2021-10-08T16:14:19Z")

</div>

Can you please merge your 2 threads?

> [@Fibonacci Numbers in Java](https://discourse.processing.org/t/fibonacci-numbers-in-java/32693):
>
> I started reading about Fibonacci Numbers in Java and was curious to know from this community about - What are the ways we can print Fibonacci Numbers in Java?

---

<div class="post-metadata">

**Author:** ![arathorn76](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@arathorn76](https://discourse.processing.org/u/arathorn76)\
**Post date:** [October 8, 2021, 10:48pm UTC](https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694/3 "2021-10-08T22:48:57Z")

</div>

> [@panahur](#):
>
> - How can I get the `N-th` Fibonacci number with `O(n)` time and `O(1)` space complexity.
> - How to calculate Fibonacci numbers without Recursion or Iteration?

There is a formula to instantly calculate the nth fibonacci number.  
Wikipedia says:  
The [partial fraction decomposition](https://en.m.wikipedia.org/wiki/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](https://wikimedia.org/api/rest_v1/media/math/render/svg/c10486267237c4d4d4b5128eaf9b2fe302d94a08)

where {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} ![arphi ={rac {1+{qrt {5}}}{2}}|0x0](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b498bd7bebdaa79ba86131a9f839f96a4e7628f) is the golden ratio and {\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}} ![{isplaystyle si ={rac {1-{qrt {5}}}{2}}}|0x0](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd35e71c5ca93eaccf91adc76f3306d645d39361) is its conjugate.

---

<div class="post-metadata">

**Author:** ![javagar](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/javagar/32/11434_2.png) [@javagar](https://discourse.processing.org/u/javagar)\
**Post date:** [October 9, 2021, 12:29am UTC](https://discourse.processing.org/t/fibonacci-numbers-in-java-o-n-time-and-o-1-space-complexity-and-without-using-recursion/32694/4 "2021-10-09T00:29:01Z")

</div>

See [Wolfram MathWorld: Binet’s Fibonacci Number Formula](https://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html).

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 …

```auto
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.