# Solving Fibonacci Number

To see the question, click **here**.

**Naive Approach**

The idea is to use a recursive approach to compute the Fibonacci sequence. If `n`

is 0 or 1, return `n`

directly, as these are the base cases for the Fibonacci sequence. For any other value of `n`

, recursively call itself to compute the sum of the two preceding Fibonacci numbers (`fib(n - 1)`

and `fib(n - 2)`

).

```
// TC: O(2^n)
// SC: O(n)
public class FibonacciNumber {
public int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String args[]) {
FibonacciNumber fibonacciNumber = new FibonacciNumber();
int n = 4;
System.out.println(fibonacciNumber.fib(n));
}
}
```

**Performance**

The time complexity of the `fib`

method is O(2^n) because for each call to the `fib`

function, it makes two recursive calls with `n-1`

and `n-2`

. This results in an exponential time complexity as the number of function calls grows exponentially with the input size. The space complexity is also O(n) because the recursion stack can grow to n levels deep. Each function call consumes space on the stack for its local variables and return address.

**Refined Approach 1**

Since there are overlapping sub-problems (i.e, fib(4) = fib(3) + fib(2), fib(3) = fib(2)+fib(1)) we will use dynamic programming. Let us use recursion combined with memoization to solve the problem. The first step is to declare an array `dp`

of size `n + 1`

and fill it with -1. Then, create a function `f`

that takes `dp`

and `i`

as parameters. Write the logic of the previous approach inside `f`

but with a slight modification and an extra base case. Before we do `f(dp, i - 1) + f(dp, i - 2)`

, we store it in `dp[i]`

to avoid recomputation. Regarding the extra base case, we check if `dp[i]`

is -1 or not. If it is not -1, that means it has already been computed. Hence, we return that value.

```
// TC: O(n)
// SC: O(n)
import java.util.Arrays;
public class FibonacciNumber {
public int fib(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, -1);
return f(dp, n);
}
public int f(int[] dp, int i) {
if (i == 0 || i == 1) {
return i;
}
if (dp[i] != -1) {
return dp[i];
}
return dp[i] = f(dp, i - 1) + f(dp, i - 2);
}
public static void main(String args[]) {
FibonacciNumber fibonacciNumber = new FibonacciNumber();
int n = 4;
System.out.println(fibonacciNumber.fib(n));
}
}
```

**Performance**

The time complexity of the `fib`

method is O(n) because we are calculating the Fibonacci number for each value from 0 to n only once and storing the result in the `dp`

array to avoid redundant calculations. The space complexity is also O(n) because we use an additional array of size n+1 to store the results of the calculated Fibonacci numbers.

**Refined Approach 2**

Let us use iteration combined with tabulation. The first step is to declare an array `dp`

of size `n + 1`

. Start with the base cases (0 and 1) and iteratively build up the solution for the nth Fibonacci number. The results are stored in the `dp`

array, which is filled sequentially from the smallest subproblems to the original problem. This approach reduces the recursion overhead from the previous approach, such as the call stack space used by recursive function calls.

```
// TC: O(n)
// SC: O(n)
public class FibonacciNumber {
public int fib(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
if (i == 0 || i == 1) {
dp[i] = i;
} else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[n];
}
public static void main(String args[]) {
FibonacciNumber fibonacciNumber = new FibonacciNumber();
int n = 4;
System.out.println(fibonacciNumber.fib(n));
}
}
```

**Performance**

The time complexity of the `fib`

method is O(n) because we are iterating through the array `dp`

of size n once to calculate the Fibonacci number for each index. The space complexity is also O(n) because we use an array `dp`

of size n to store the Fibonacci numbers.

**Efficient Approach**

We will use Binet's formula to find the n-th Fibonacci number.

$$Fib(n) = (Φ^n - φ^n)/√5$$

$$ ϕ = (1 + √5) / 2$$

$$ φ = (1 - √5) / 2$$

```
// TC: O(1)
// SC: O(1)
public class FibonacciNumber {
public int fib(int n) {
double sqrt5 = Math.sqrt(5);
double phi = (1 + sqrt5) / 2;
double psi = (1 - sqrt5) / 2;
return (int) Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5);
}
public static void main(String args[]) {
FibonacciNumber fibonacciNumber = new FibonacciNumber();
int n = 4;
System.out.println(fibonacciNumber.fib(n));
}
}
```

**Performance**

The time complexity of the `fib`

method is O(1) because the Fibonacci number is calculated in constant time regardless of the input value of n. The space complexity is also O(1) because only a constant amount of extra space is used for storing the square root of 5, phi, and psi.

Thank you for reading!

Check out other DSA patterns **here**.

You can support me by **buying me a book****.**