Algorithm - Dynamic Programming (DP)

DP is an algorithm design techniques that involves finding a solution to problems using “controlled brute force” problem solving in polynomial time. In this article we will explore Memoization.

Example : Fibonacci - exponential time

$F(n) = F(n-1) + F(n-2)$

Fibonacci algorithm implementation with a exponential running time.

The exponential work come from having to repeatedly calculating the sub-problem for each sequence in F(n). Below depicts a tree representing the work needed to calculate the F(n-1) and F(n-2) Fibonacci sequence.

We can see that solutions for a sub-problem can be reused. The algorithm can be improved by reusing the solutions calculated from a sub-problem, technique known as Memoization.

Time complexity (exponential time)

Below shows the time complexity for exponential time Fibonacci algorithm. We first look at the cost of the sub-problem. In Fibonacci, the sub-problem is repeated for each sequence (F1, F2, …, Fn).

$T(n) = T(n-1) + T(n-2) + \theta(1)$

The upper bound for time complexity can be expressed as:

$T(n) = T(n-2) + T(n-2) + \theta(1)$ or $T(n) = 2T(n-2) + \theta(1)$

So the time complexity for all the sub-problems for F(n):

$T(n) \ge 2 ^ {(n/2)}$ ... or ... $\large \theta (2 ^ n)$

Memoization

Memoization caches the results for a sub-problem so that work is not repeated. For an exponential amount of work, Memoization can significantly improve algorithm performance. Below is an example of using Memoization to improve the Fibonacci algorithm.

Bottom-up

Bottom-up approach is the same as Dynamic Programming with Memoization. The only difference is that Bottom-up approach does not use recursion (no call stack tree). In the example of finding nth Fibonacci, Bottom-up builds the values towards nth sequence.

Another way of looking at Bottom-up approach is a Topological sort from F1 to Fn.

Time complexity (Memoization / Bottom-up)

The time complexity is the sum of all the sub-problems. Asymptotically We can treat the sub-problem work as constant time:

$T(n) = n (T(\text{work sub-problem}))$

Note that Memoized calls are constant time, so the complexity is dependent on the number of non-memoized operations needed to calculate F(n). This means the complexity is linear time … $\theta(n)$