Fibonacci calculation

Fibonacci.java

public class Fibonacci {
    // Recursive approach without optimizations
    // Recursive: O(2^n) time, O(n) space
    public static long fibonacciRecursive(int n) {
        return n <= 1 ? n : fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }

    // Iterative: O(n) time, O(1) space
    public static long fibonacciIterative(int n) {
        if (n <= 1) return n;
        long prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }

    public static void findFib(int n) {
        long start = System.nanoTime();
        long iterative = fibonacciIterative(n);
        double iterativeTime = (System.nanoTime() - start) / 1_000_000.0;

        System.out.printf("Iterative (n=%d): %d, Time: %.3f ms%n", n, iterative, iterativeTime);

        start = System.nanoTime();
        long recursive = fibonacciRecursive(n);
        double recursiveTime = (System.nanoTime() - start) / 1_000_000.0;

        System.out.printf("Recursive (n=%d): %d, Time: %.3f ms%n", n, recursive, recursiveTime);
    }

    public static void main(String[] args) {
        findFib(10);
        findFib(45);
        // findFib(100); - I will never call this method with recursive approach
    }
}

Output

Iterative (n=10): 55, Time: 0.001 ms
Recursive (n=10): 55, Time: 0.006 ms

Iterative (n=45): 1134903170, Time: 0.001 ms
Recursive (n=45): 1134903170, Time: 2581.651 ms

To optimize the recursive Fibonacci function using memoization, we can store previously calculated Fibonacci numbers in a cache to avoid redundant computations. This reduces the time complexity from O(2^n) to O(n)

Memoization: The recursive function uses a Long[] array to cache results. Each Fibonacci number is computed once and stored, reducing the time complexity to O(n) as each number is calculated only once. Space complexity is O(n) for the memoization array and recursion stack.

    // Memoized recursive: O(n) time, O(n) space
    public static long fibonacciRecursiveMemoized(int n, Long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != null) return memo[n];
        memo[n] = fibonacciRecursiveMemoized(n - 1, memo) + fibonacciRecursiveMemoized(n - 2, memo);
        return memo[n];
    }

    // Memoized recursive
    Long[] memo = new Long[n + 1];
    long recursiveMemo = fibonacciRecursiveMemoized(n, memo);

// findFib(100); - I will never call this method with a recursive approach

Want to know how long it will take with n =100?