Question

Write the recurrence relation of the following recursive algorithm. What is the complexity

of the algorithm?
int Test(int n)
int result;
begin
if (n==1) return (1);
result = 1;
for i=1 to n do
result = result + Test(i-1);
return (result);
end

Answer 1

The recurrence relation of the given recursive algorithm can be written as:T(n) = T(n-1) + 1 + T(n-2) + 1 + T(n-3) + 1 + ... + T(1) + 1where T(1) = 1The first term T(n-1) represents the recursive call of the function with input n-1, and the for loop executes n times, where for each i, it calls Test function with input i-1.To find the time complexity, we can expand the recurrence relation as follows:T(n) = T(n-1) + 1 + T(n-2) + 1 + T(n-3) + 1 + ... + T(1) + 1

= [T(n-2) + 1 + T(n-3) + 1 + ... + T(1) + 1] + 1 + [T(n-3) + 1 + T(n-4) + 1 + ... + T(1) + 1] + 1 + ...

= [T(n-2) + T(n-3) + ... + T(1) + (n-2)] + [T(n-3) + T(n-4) + ... + T(1) + (n-3)] + ...

= (1 + 2 + ... + n-1) + [T(1) + T(2) + ... + T(n-2)]

= (n-1)(n-2)/2 + T(n-1)Therefore, the time complexity of the algorithm can be written as O(n^2), because the first term is equivalent to the sum of the first n-1 integers, which is of order O(n^2), and the second term is T(n-1).