Question

Consider the following algorithm BAR that gets a positive integer and works as follows:

BAR(int n):

- if (n <=0 ), return 0;

- else, return (n - BAR(BAR(n-1)));

(A.) What will be the output of BAR(3)?

(B.) Write an algorithm that has the same functionality as BAR, so that the runtime of BAR(n) is O(n)?

Answer 1

Question A.

BAR(0) = 0
BAR(1) = 1 - BAR(BAR(0)) = 1 - BAR(0) = 1 - 0 = 1
BAR(2) = 2 - BAR(BAR(1)) = 2 - BAR(1) = 2 - 1 = 1
BAR(3) = 3 - BAR(BAR(2)) = 3 - BAR(2) = 3 - 1 = 2

So, the output of BAR(3) would be 2.

Question B.

Approach: We can use dynamic programming bottom up approach to calculate BAR(n) in O(n) running time.

O(N) algorithm:

Step 1: Take an array dp of size n+1, i.e. dp[n+1];
Step 2: dp[0] = 0;
Step 3: for i = 1 to n
dp[i] = i - dp[dp[i-1]];
end of for loop
Step 4: dp[n] is the answer.

- The loop takes O(n) time to run. So, the time complexity of the above algorithm is O(n). Also, the space complexity of the above algorithm is O(n) as we are taking an array of size n+1.
- dp[i] array stores the value of BAR( i ).

If the answer helped please upvote, it means a lot and for any query please comment.