Analyze the following algorithm int fooint n int left int ri

Analyze the following algorithm int foo(int n, int left, int right) {int rVal = 0; for (int i = 0; i 2) {int mid = left + (right - left)/2; return foo(n, left, mid -1) + foo(n, mid + 1, right);} return 1;}

Solution

The above algorithm is used identify mid point in the sequence (given left and right values).

If no of indexes from left to right is greater than 2 then calculate mid from all the recursive calls of the same function.