Please read the new rule regarding the restriction on the use of AI tools. ×

How I can find the time complexity of this algorithm?

Revision en1, by annoying, 2020-12-23 12:33:54

I tried to solve the problem on codechef problem COINS. And I have write the following code:

#define long long LL

map<LL,LL> data;   //map DS to store key:value pair
LL solve(LL n){
    if(n<=2)
      return n;
    if(data[n]==0){
      data[n] = max(n,(solve(n/4)+solve(n/3)+solve(n/2)));
    }
    return data[n];
} 

This Link have a very nice discussion on time complexity of this code but I am not able to get any of that. can any one help me out to explain me in detail how can I approch to find the time complexity of this specific problem.

Tags #recursion,dp, #complexity, time complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English annoying 2020-12-23 12:33:54 758 Initial revision (published)