C++

Forum

 
Time Complexity of a Recursive Function with a Reducing Parameter

bydrachen (57)
What's the big O notation and how can I calculate it? I'm new to this.

Is there a general rule of this?

1
2
3
4
5
6
7
8
9
 
  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);
}
lastchance (6980)
O(n) if m is positive.

Never ending if m is negative or zero.
Last edited on
jonnin (11437)
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 (?).
Last edited on
Topic archived. No new replies allowed.