# algorithms – How to analysis the complexity of this LIS program?

I found a pseudocode online and I don’t know why the complexity of it is $$O(2^N)$$, according to the site.

Given a fixed `curr`, the for-loop in `lis_ending_here(...)` will recursively call `curr` times itself will new `curr` range from `0 to curr-1`, then I stuck here and don’t know what’s the next step to get the conclusion $$O(2^N)$$. You can also provide me resource (i.e. book name) which is about the technique to analysis the complexity of recursion, since I don’t know what are the beginner friendly ones.

``````int lis_ending_here(int arr(), int curr)
{
// Only one subsequence ends at first index, the number itself
if(curr == 0)
return 1
int ans = 1
for(i = curr-1 to 0, decrement of -1)
if(arr(i) < arr(curr))
ans = max(ans, 1 + lis_ending_here(arr, i))
return ans
}
int longest_increasing_subsequence(int arr(), int N)
{
// Because a single number can be a subsequence too
int max_ans = 1
for(i = 0 to N-1)
max_ans = max(max_ans, lis_ending_here(arr, i))
return max_ans
}
``````