Why is this LIS code O(2^n) and not O(n^n)? I'm confused
Hey everyone, I'm new to DP
I’m practicing the Longest Increasing Subsequence (LIS) problem and wrote this recursive solution. I keep reading that this approach has a time complexity of O(2^n), but looking at the for loop inside the recursive function, my brain tells me it should be O(n^n).
Here is the snippet:
def solve(i, last):
if i == N:
return 0
best = 0
for j in range(i, N): # Loop from current index to end
if nums[j] > last:
best = max(best, solve(j + 1, nums[j]) + 1)
return best
My logic is: if we are at index i and we loop N times, and the recursion depth can be N, shouldn't that be N * N * N * N ... (N ^ n)?
Where is my math going wrong? Why does it settle at 2^n? Is it because the loop range (i, N) shrinks as we go deeper?
Appreciate any help in visualizing this!