help to find complexity

Правка en3, от Agassaa, 2015-11-10 11:30:26

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

Теги math, combinatorics, thanks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Agassaa 2015-11-10 11:30:26 374
en2 Английский Agassaa 2015-11-10 02:06:26 9
en1 Английский Agassaa 2015-11-10 02:05:25 377 Initial revision (published)