CODEWITHSUNDEEP
recursionbig-otime-complexity
dead programmer
dead programmer

Reputation: 4365

Calculating the complexity of the function

I have writing a function for calculating the length of longest increasing sequence. Here arr[] is array of length n. And lisarr is of length of n to store the length of element i.

I am having difficulty to calculate recurrence expression which is a input for master theorem.

int findLIS(int n){
        if(n==0)
            return 1 ;
        int res;
        for(int i=0;i<n;i++){
            res=findLIS(i);
            if(arr[n]>arr[i] && res+1>lisarr[n])
                lisarr[n]=res+1;
        }
        return lisarr[n];
    }

Please give the way to calculate the recurrence relation. Should it be T(n)=O(n)+T(1)?

Upvotes: 0

Views: 42

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15241

It is O(2^n). Let's calculate exact number of iterations and denote it with f(n). Recurrence relation is f(n) = 1 + f(n-1) + f(n-2) + .. + f(1) + f(0), with f(1)=2 and f(0)=1, which gives f(n)=2*f(n-1), and finally f(n)=2^n.

Proof by induction:

Base n=0 -> Only one iteration of the function. Let us assume that f(n)=2^n. Then for input n+1 we have f(n+1) = 1 + f(n) + f(n-1) + .. + f(1) + f(0) = 1 + (2^n + 2^(n-1) + .. + 2 + 1) = 1 + (2^(n+1) - 1)=2^(n+1).. Number one at the beginning comes from the part outside of the for loop, and the sum is the consequence of the for loop - you always have one recursive call for each i in {0,1,2,..,n}.

Upvotes: 2

Related Questions