In Java Language Consider the following algorithm A is an ar

In Java Language

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 rec(n 1)

         A[n] 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.

Thank you!

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 show that

T(n) = T( n - ( k + 1) ) + (k+1) is true for k + 1 too ..

T(n) = 0(n)