Complexity of a dynamic programming versus memoization in this case?

Question

Here's a little exercise i'm working on about dynamic programming. I have the following function :

I have to program this function with two approaches (top-down with memoization and bottom-up).

Here's what I currently do for bottom up:

    public static int functionBottomUp (int n){
            int [] array = new int[n+1];
            array[0] = 1;
            for(int i = 1; i < array.length; i++){
                if(i == 1)
                    array[i] = array[i - 1];
                else {
                    for(int p = 0; p < i; p ++)
                        array[i] += array[p];
                }
            }
            return array[n];
   }

And for memoization :

public static int functionMemoization(int n){
        int[] array = new int[n+1];     
        for(int i = 0; i < n; i++)
            array[i] = 0;
        return compute(array, n);
    }

    private static int compute(int[] array, int n){
        int ans = 0;
        if(array[n] > 0)
            return array[n];
        if(n == 0 || n == 1)
            ans = 1;
        else 
            for(int i = 0; i < n; i++)
                ans += compute(array, i);
        array[n] = ans;
        return array[n];
    }

---

I get correct outputs for both but now i'm struggling myself to calculate the complexities of both.

First the complexity of f(n) is 2^n because f(3) make 7 calls to f(0) and f(4) make 15 calls to f(0) (I know this is not a formal proof but this is just to give me an idea).

But now i'm stuck for calculating the complexity of both functions.

---

Bottom-Up :

I would say that the complexity is O(n) (because of the for(int i = 1; i < array.length; i++)) but there is this inner loop for(int p = 0; p < i; p ++) and I don't know if this modifies the complexity.

Memoization :

Clearly this is a most O(n) because of the first loop which initialize the array. But I don't know how the compute function could modify this complexity.

Could someone clarify this for me ?

Answer 1

Let's take a look at your functions. Here's the bottom-up DP version:

public static int functionBottomUp (int n){
        int [] array = new int[n+1];
        array[0] = 1;
        for(int i = 1; i < array.length; i++){
            if(i == 1)
                array[i] = array[i - 1];
            else {
                for(int p = 0; p < i; p ++)
                    array[i] += array[p];
            }
        }
        return array[n];
}

To count up the work that's being done, we can look at how much work is required to complete loop iteration i for some arbitrary i. Notice that if i = 1, the work done is O(1). Otherwise, the loop runtime is taken up by this part here:

for(int p = 0; p < i; p ++)
    array[i] += array[p];

The time complexity of this loop is proportional to i. This means that loop iteration i does (more or less) i work. Therefore, the total work done is (approximately)

1 + 2 + 3 + ... + n = Θ(n²)

So the runtime here is Θ(n²) rather than O(n) as you conjectured in your question.

Now, let's look at the top-down version:

public static int functionMemoization(int n){
    int[] array = new int[n+1];     
    for(int i = 0; i < n; i++)
        array[i] = 0;
    return compute(array, n);
}

private static int compute(int[] array, int n){
    int ans = 0;
    if(array[n] > 0)
        return array[n];
    if(n == 0 || n == 1)
        ans = 1;
    else 
        for(int i = 0; i < n; i++)
            ans += compute(array, i);
    array[n] = ans;
    return array[n];
}

You initially do Θ(n) work to zero out the array, then call compute to compute all the values. You're eventually going to fill in all of array with values and will do so exactly once per array element, so one way to determine the time complexity is to determine, for each array entry, how much work is required to fill it. In this case, the work done is determined by this part:

for(int i = 0; i < n; i++)
    ans += compute(array, i);

Since you're memoizing values, when determining the work required to evaluate the function on value n, we can pretend each recursive call takes time O(1); the actual work will be accounted for when we sum up across all n. As before, the work here done is proportional to n. Therefore, since n ranges from 1 to n, the work done is roughly

1 + 2 + 3 + ... + n = Θ(n²)

Which again is more work than your estimated O(n).

However, there is a much faster way to evaluate this recurrence. Look at the first few values of f(n):

• f(0) = 1
• f(1) = 1
• f(2) = 2
• f(3) = 4
• f(4) = 8
• f(5) = 16
• ...
• f(n) = 2^n-1

Therefore, we get that

• f(0) = 1
• f(n) = 2^n-1 if n > 0

Therefore, the following function evaluates f time:

int f(int n) {
    return n == 0? 1 : 1 << (n - 1);
}

Assuming that you're working with fixed-sized integers (say, 32-bit or 64-bit integers), this takes time O(1). If you're working with arbitrary-precision integers, this will take time Θ(n) because you can't express 2^n-1 without writing out Θ(n) bits, but if we're operating under this assumption the runtimes for the original code would also need to be adjusted to factor in the costs of the additions. For simplicity, I'm going to ignore it or leave it as an exercise to the reader. ^_^

Hope this helps!