Seems very hard to find out the time complexity of this simple program

Question

I have the code below to mimic a recursive behavior of an algorithm, because I failed to figure out the time complexity of that algorithm:

int M(int n)
{
    int result = 1;
    for (int i = n-1; i >= 0; --i)
    {
        result += M(i);
    }
    return result;
}

According to my understanding, I have drawn the tree below to illustrate the algorithm :

(The input n is 3 in the picture). I think the number of nodes in the tree is the complexity of the algorithm. If the input is n, what's the time complexity would be? Thanks!

Answer 1

My background is not CS but I can provide you an easy way to look at this problem,

So I took a paper and pen and started out with different values of n.

n = 2, cycles = 4
n = 3, cycles = 8
n = 4, cycles = 16
n = 5, cycles = 32.

You can clearly see the cycles = 2^N and therefor we can conclude that time complexity of this problem is O(2^N).

Now to look at this in another way could be

We know that

f(0) = 1
f(1) = f(0) + 1 = 2
f(2) = f(1) + f(0) + 1 = 4
...
f(N) = f(N-1) + f(N-2) .. + f(0) + 1 = 2^N.

So now that you have a recurrence relation similar to how you calculate factorial, you can do maths or create a program to measure time complexity of the problem.

Hope that my answer helps you in understanding the theory of calculating time complexity.

Answer 2

Your tree diagram is illuminating. Can you see the line of symmetry? The tree for M(n) looks like two copies of the tree for M(n-1). Thus the number of nodes in the tree is 2**n, and the complexity of the algorithm O(2**n).