Time Complexity of a Recursive Function with a Reducing Parameter-CodePudding

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?

CodePudding user response：

O(n). I'm a student too, so take this with a grain of salt. If it's wrong I will delete this. But I think it's right. Try looking up the theory and understanding it so you can apply this to all problems.

It will take n-10 loops n-m loops 1 loop, which is about n, and in big O you ignore small error - e.g., it's closer to n than to n^2.

CodePudding user response：

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 (?)."