Time complexity of dp problems

1

how do we find out the time complexity of dynamic programming problems.Say we have to find timecomplexity of fibonacci.using recursion it is exponential but how does it change during while using dp?

2

how do we find out the time complexity of dynamic programming problems.

Just like any other program…the times the loops iterate respective to n or values of array a_i ( in case of arrays where n being size of the array and a_i being values in the array a ).

Also, note that time taken by one program with O(n) complexity is same time as another program with same O(n) complexity. As said, it totally depends on the ranges(“constraints”) given in the problem / question.

To your question,

Say we have to find timecomplexity of fibonacci.using recursion it is exponential but how does it change during while using dp

Like mentioned, the traditional way uses recursion function,

f(n) = f(n-1) + f(n-2)

                            fib(5)   
                     /                 \        
               fib(4)                  fib(3)   
             /      \                /       \
         fib(3)      fib(2)         fib(2)    fib(1)
        /   \          /    \       /      \ 
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \ 
fib(1) fib(0)

The complexity is said to be O(2^n) although it’s O(1.6^n) (golden ration = 1.61) and lets not go deep about it.

If you could notice fib(3) is already computed in the left sub tree and we don’t need to compute it again in right sub tree instead we use memoization, to store the values that we already computed and voila the complexity is reduced to O(n). We simply compensated memory in exchange for computation time. However, memoization is different from DP approach…but I thought it would be better for you to visualize on how complexity changes.

Again, I want to highlight that, calculation of DP approach computational complexities are no different from how you compute normally.

1 Like
3

It’s always easier to calculate the complexity of any iterative algorithm and DP is not an exception.

I agree that if you think of a recursive DP solution, sometimes it can be a bit difficult to find the complexity. You can look at the number of UNIQUE states that are possible, that would give you an idea about the complexity. For Fibonacci example, number of unique Fibonacci numbers you need can be at most N. So it’s of order O(N).

1 Like