CODEWITHSUNDEEP
c++algorithmdata-structurestime-complexity
Mohd Shibli
Mohd Shibli

Reputation: 978

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

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.

Upvotes: 0

Views: 529

Answers (1)

OmG
OmG

Reputation: 18838

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).

Upvotes: 2

Related Questions