Fibonacci – Normal vs Dynamic programming Huge Time complexity Difference

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.

2 comments

  • Hello NgDeveloper Team,

    Nice blog! I am editor at Java Code Geeks (www.javacodegeeks.com). We have the JCG program (see http://www.javacodegeeks.com/join-us/jcg/), that I think you’d be perfect for.

    If you’re interested, send me an email to eleftheria.drosopoulou@javacodegeeks.com and we can discuss further.

    Best regards,
    Eleftheria Drosopoulou

  • Lara4143

    Мадонна, икона поп-музыки и культурного влияния, продолжает вдохновлять и поражать своей музыкой и стилем. Её карьера олицетворяет смелость, инновации и постоянное стремление к самовыражению. Среди её лучших песен можно выделить “Like a Prayer”, “Vogue”, “Material Girl”, “Into the Groove” и “Hung Up”. Эти треки не только доминировали на музыкальных чартах, но и оставили неизгладимый след в культурной и исторической панораме музыки. Мадонна не только певица, но и икона стиля, актриса и предприниматель, чье влияние простирается далеко за рамки музыкальной индустрии. Скачать mp3 музыку 2024 года и слушать онлайн бесплатно.

Leave a Reply