Consider the following algorithm A is an array of size n Alg

Consider the following algorithm. A is an array of size n. Algorithm rec(n) In: Integer value n. if n = 0 then return 1 else {i leftarrow rec(n - 1) A[n] leftarrow I return i} Write a recurrence equation for the time complexity of this algorithm. Solve the above recurrence equation by repeated substitution and give the order of the time complexity.

Solution

T(n) = T(n-1) + 1

T(n) = T(n-2) + 2 = T(n-3) + 3
Assume T(n) = T(n-k) + k
T(n) = T(n-k-1) + k + 1 using original recurrence relation

By induction we have shown that
T(n) = T(n-(k+1)) + (k+1) is true for k+1 too..
T(n) = O(n)

Hi I used induction hypothesis. Suppose something true for i=k then if it\'s true for i=k+1. Then equation/relation is bound to be true. Here, I supposed relation to be true for i = k then using original problem, I showed my derived formula so it\'s correct