Calculating time complexity of a recursive function having a loop inside it

Question

I was working on a simple problem and I came up with a recursive function in C++, below is my function.

void test(int arr[],int n,int x = 0){
    cout<<arr[x];
    for(int i = x+1;i < n;i++){
        test(arr, n, i);
    }
}

I wonder what will be the time complexity of the above function if anyone can calculate the time complexity for the above method it will be a great help in improving my function.

Recursion can be seens as a kind of fancy loop. So if you could rewrite the recursion into a loop then it might be easier. — Some programmer dude
– Some programmer dude, Commented Jul 8, 2018 at 13:22
Instead of x = x + 1; test(arr, n, x); why don't you just write test(arr, n, i);? It's equivalent, but simpler and easier to understand. — DodgyCodeException
– DodgyCodeException, Commented Jul 8, 2018 at 13:28

OmG · Accepted Answer · 2018-07-08 14:10:05Z

2

You can write its recurrent relation likes the following:

 T(n) = T(n-1) + T(n-2) + ... + T(1) + 1

Indeed T'(x) is T(n - x) and T(1) = 1 (The last one in the realtion is is for cout). We can see:

T(2) = T(1) + 1 = 2
T(3) = T(2) + T(1) + 1 = 2 + 1 + 1 = 4
T(4) = 4 + 2 + 1 + 1 = 2^2 + 2^1 + 2^0 + 1 = 8
T(5) = 8 + 4 + 2 + 1 + 1 = 2^3 + 2^2 + 2^1 + 2^0 + 1 = 16
.
.
.
T(n) = 2^{n-2} + 2^{n-1} + ... + 2^0 + 1 = 2^{n-1}

Hence, T(n) = \Theta(2^n).

edited Jul 8, 2018 at 14:10

answered Jul 8, 2018 at 13:54

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Mohd Shibli Over a year ago

How you are using T(n-1) ?? It should be n+1 I guess?? If I am wrong please correct me

OmG Over a year ago

@MohdShibli As I said T(n-1) is time complexity for x = 1 and generally, T(i) is for x = n - i.

Mohd Shibli Over a year ago

Maybe the complexity will be O(k^n) as the loop will run k times for worst case

Collectives™ on Stack Overflow

Calculating time complexity of a recursive function having a loop inside it

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related