I am unable to predict the time complexity of this question. Please help me
Predict teh Time Complexity
Here is the question text : 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); } } }
@gptradhika1208
it will be O(n*m)
time complexity for such dp solution is computed -> number of states * time of transistion from one state to another.
here number of states are N * M
time to transit from one state to other is O(1) so overall
time complexity -> O(N*M 1) -> O(NM)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.