It’s difficult to determine the time complexity of this simple program.

Question

I have the code below to mimic the recursive behavior of an algorithm because I was unable to determine the time complexity of this algorithm:

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

In my opinion, I have cited the tree below to illustrate the algorithm:

(input n is 3 in the figure). I think the number of nodes in the tree is the complexity of the algorithm. If the input signal is n, what will be the time complexity? Thanks!

Answer 1

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

So, I took the paper and pen and started 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 therefore we can conclude that the time complexity of this problem is O (2 ^ N).

Now look at it differently could

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 repetition ratio similar to how you calculate factorial, you can do the math or create a program to measure the time complexity of the problem.

I hope that my answer will help you understand the theory of calculating time complexity.

Answer 2

Your tree chart is lit. Do you see a 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 is O (2 ** n).