Hi,↵
↵
I am a beginner, please help me find the complexity of the following code:↵
↵
↵
~~~~~↵
int lim=9;↵
int vis[200];↵
void rec(int x) ↵
{↵
if(x==100) return;↵
if(vis[x]==1) return;↵
vis[x]=1;↵
for(int i=x;i<100;i++)↵
{↵
if(i-x > lim) break;↵
rec(i+1);↵
}↵
}↵
int main()↵
{↵
rec(0);↵
}↵
~~~~~↵
↵
Thanks!↵
↵
↵
**UPD:**↵
↵
I thought that it would be a math problem, but use of memorization array made the complexity simpler, so I want to slightly modify the above code: what would be the complexity if we didn't use vis[200] array?↵
↵
I analyzed it a bit, and the problem turns out to be: how many ways to sum to 'n' using values not more than 'lim'↵
↵
Anyone help please! Thanks↵
↵
I am a beginner, please help me find the complexity of the following code:↵
↵
↵
~~~~~↵
int lim=9;↵
int vis[200];↵
void rec(int x) ↵
{↵
if(x==100) return;↵
if(vis[x]==1) return;↵
vis[x]=1;↵
for(int i=x;i<100;i++)↵
{↵
if(i-x > lim) break;↵
rec(i+1);↵
}↵
}↵
int main()↵
{↵
rec(0);↵
}↵
~~~~~↵
↵
Thanks!↵
↵
↵
**UPD:**↵
↵
I thought that it would be a math problem, but use of memorization array made the complexity simpler, so I want to slightly modify the above code: what would be the complexity if we didn't use vis[200] array?↵
↵
I analyzed it a bit, and the problem turns out to be: how many ways to sum to 'n' using values not more than 'lim'↵
↵
Anyone help please! Thanks↵
