int func (int n, int m)
{
if (n<1)
return n;
else if (n<10)
return func(n-m, m);
else
return func(n-1, m);
}
This is the function. What's the big O notation and how can I calculate it? I'm new to this.
Is there a general rule of this?
This answer is from another person called jonnin in cplusplus com. Here is:
"recursion is just a type of loop, you treat it the same way. The pain point is that sometimes its hard to understand the loop, but you can write obnoxious normal loops too, so that is a problem on both sides.
this is basically this loop for counting the real work done: (it can take a while to see it if new to recursion) while(n > 10) n --;
which does nothing if N is < 10 and decrements at O(n) otherwise. You can be specific about the N<10 special cases but big O is all about the general sense of the thing, not the gory details. If you want to layout all the details, in like a PHD paper on some exotic function, you can dig deeper and do so, but most big-O analysis is a cruder tool. As a teacher I would accept O(n) for N>10 else O(1).
If M is allowed to be 0/negative, as noted, never ends, and you should note that too. Most likely this is bad input, and should not effect the answer (?)."