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.