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

Viewed 253

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 : when n is 3

(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!

3 Answers

By tracing the code snippet the time complexity would be O(2^n)

I have attached a image you can check it.

Related