Question

2. Consider the function george (int n) computed by the following recursive C++ code. int george (int n) assert (n >= 0) if (n < 2) return 1; else return 2*george ((n+1)/2)+2*george (n/2)+2 george((n-1)/2)+2*george (n/2-1); (c) Design a memoization algorithm to compute george(n) for any given n. You do not have to write C++ code. This algorithm should be much faster than the dynamic programming algorithm. What is its time complexity?

Answer 1

See, we will follow bottom up approach in building memoization algorithm for this problem. Bottom up approach means, first we will calculate base values and then then we will calculate higher values from those base values. We call it memoization because we avoid repetitive calculation of base values again and again by saving those base values in an array.

Lets have insight of problem-

Note- Below image is showing just one recursive call of george(4) function.

We can see that george(2) and george(1) are calculated twice during recursive call. we are unnecessarily calculating george(2) and george(1) again and again as we go more deep into recursive tree.

geogc)

So one efficient approach is , we can store values which are calculated once into an array. So in future we can use that value without doing redundant computation again and again.

We will declare an array where arrar[i] will store value of grorge(i).

Algorithm-

1. Declare an array of size n.

2. Fill base values array[0]=george(0)=1 and array[1]=george(1)=1.

3. For any value of n>2, ans=2*array[(n+1)/2]+ 2*array[n/2]+2*array[(n-1)/2]+2*array[(n/2)-1].

4. Store value calculated for george(n) at array[n].

Complexity is O(n) because for any value greater than 2, we are roughly accessing n times contents of array and array access is possible in constant time (O(1)).

As we have seen that we have built array form base values, that's why this approach is called bottom up approach.