Why its time com.id not n2

#1

predict the complexity of the code:

vector<vector > v(100,vector (100,-1) );
int func(int n,int m)
{
if((n==0)||(m==0))
{
return 0;
}
else
{
if(dp[m][n]!=-1)
{
return dp[m][n];
}
else
{
return func(n-1,m-2)+func(n-2,m-1);
}

  }

}

#2

@anshulgurawalia
assuming dp is initialized with -1 , we are computing the function for state (n,m) only once as repetative cases are handled by memoization and for every state (n,m) we are running a doubly nested loop so for every state we will have N * M operations (for loops) and there are N * M unique states so overall operations is (N * M) * (N * M) which is closest to O(n^4)

#3

there is no memoization in the code they only declare a 2d array and not storing the returned value into the dp

#4

ohh
yes they are not using the dp
so time complexity will be exponential
2^n

#5

why not n2 for the worst case for a single value we have to traverse the whole array and we have total n element so its time com. is n2 ??

#6

it is 2D array so no of elments is not n
n*m (no of rows * no of columns)