Agassaa's blog

help to find complexity
By Agassaa, history, 9 years ago, In English

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

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, In this code ,you start from 0 and for each number you call "rec" for next 8 numbers and after making sure you haven't seen that number before , you do the "for" for it. But if you trace your code , you see that after calling the "rec" for 0 , it call "rec" for 1 and "rec" for 1 calls "rec" for 2 and ...... this mean your doing an O(n) algorithm 'cause you visit each number once and you see all numbers from zero one by one.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I would say it's O(n * lim), where n = 100 in this example.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"how many ways to sum to 'n' using values not more than 'lim'"

yep you're right. The way of such division is about 2 ^ n. "lim" will be meaningless — because it's huge anyway (if lim is 2, the way of division is Fibonacci(n) = 1.618 ^ n)

→ Reply