Fibonacci – Normal vs Dynamic programming Huge Time complexity Difference

Algorithms, Java

Dynamic programming, guarantees to find the optimal solution of a problem if the solution exists. It basically follows these steps,

  • Divide the main complex problems into sub-problems
  • Saves the sub-problem result found
  • Apply the saved result rather than re-computing the solution again.

Let’s understand the differences it provides (time complexity difference) with dynamic programming approach,

Fibonacci Program – Normal & Dynamic Programming:


import java.time.LocalDateTime;

public class Fibonacci {

    public static void main(String[] args) {
        // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
        int n = 10;

        // normal
        long ldtStart = LocalDateTime.now().getNano();
        int fibo = nthFibo(n);
        System.out.println(fibo);
        long ldtEnd = LocalDateTime.now().getNano();
        System.out.println("Total Execution Time: " + (ldtEnd - ldtStart));

        // with dynamic programming
        long ldtStartDP = LocalDateTime.now().getNano();
        int fiboDP = nthFiboDP(n);
        System.out.println(fiboDP);
        long ldtEndDP = LocalDateTime.now().getNano();
        System.out.println("Total Execution Time for DP: " + (ldtEndDP - ldtStartDP));
    }

    private static int nthFibo(int n) {
        if (n <= 1) {
            return n;
        }
        return nthFibo(n - 1) + nthFibo(n - 2);
    }

    private static int nthFiboDP(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

If I run the above code, then my output is, (here execution time is very less in both the approaches)

55
Total Execution Time: 0
55
Total Execution Time for DP: 0

Now with the n value as = 20,

6765
Total Execution Time: 999700
6765
Total Execution Time for DP: 0

Now with the n value as n =30,

832040
Total Execution Time: 3998800
832040
Total Execution Time for DP: 0

And strange problem here is if the n value is greater than 30 then time complexities getting higher and higher and at n = 100 literly in my machine nothing works for few mins and completely hangs out.

Now, in order to address all these stuff’s in a efficient way, dynamic programming helps really in a greater extend.

Hope this simple program helps you to understand how dynamic programming brings much better improvements from the time complexities perspective.

11 comments

11 comments

Leave a Reply