CODEWITHSUNDEEP
c++recursion
chinmay kumar
chinmay kumar

Reputation: 41

what is the time complexity for this recursive function?

void solve(string op, int n, int zeros, int ones)
{
    if(n==0){
        cout<<op<<" ";
        return;
    }
    string op1 = op;
    op1.push_back('1');
    solve(op1, n-1, zeros, ones+1);
    if(ones > zeros){
        string op2 = op;
        op2.push_back('0');
        solve(op2, n-1, zeros+1, ones);
        return;
    }

}

what is the time complexity for the solve function? is it O(2^N)? can someone please explain how you approach to find complexities for recursive functions?

link to question: https://www.geeksforgeeks.org/print-n-bit-binary-numbers-1s-0s-prefixes/

Upvotes: 3

Views: 225

Answers (2)

rhaport
rhaport

Reputation: 550

So, we want to estimate the worse case here. The worse case would be if the condition (ones > zeros) always returns to true. Is it possible? Yes, if ones-zeros >= n. Since I don't know the context of your task, I may assume it.

Let T(n) is the complexity of your function. Your function calls itself with (n-1) two times. That means,

T(n) = T(n-1) + T(n-1) + c

where c is a constant for routines you are doing else like appending '1' or '0', condition evaluating etc. what is not depended on n.

So,

T(n) = 2T(n-1) + c =
     = 2(2T(n-2) + c) + c = 4T(n-2) + 3c = 
     = 4(2T(n-3) + c) + 3c = 8T(n-3) + 7c = 
     = ...
     = 2^k*T(n-k) + (2^k-1)*c

so if (n-k) == 0, you are done, as T(0) = z. So, we are done when k == n. Regarding z it is not obvious. In the current implementation we do output a string which is O(n). If we would just count strings it would be O(1). If we printing is essential the final complexity would be O(n2^n) if not then O(2^n)

That means,

T(n) = z*2^n + (2^n - 1)*c = O(z2^n)

[UPDATE1]

after realizing the real problem which was not clear from the code snippet but became clear after reading the info from the provided link, I would say that the complexity is different.

The calculation above is still true under assumptions was made.

Now, to this problem. We want to find all sequences of 1 and 0 of length n where each prefix contains 1's not less than the number of 0's in this prefix.

The algorithm provides the solution to this problem. As you can notice at each recursive call, the algo adds either 0 or 1 to the resulting sequence. That means the number of recursive calls is exactly the umber of symbols in the resulting strings.

We know that the length of each resulting string is n. So, we need to figure out the number of strings. Let's take a look what your program finds for different n's:

n    | number of strings 
-----------------------
1    |    1
2    |    2
3    |    3
4    |    6
5    |    10
6    |    20
7    |    35
8    |    70

So, if you look carefully, you will recognize that these are binomial coefficients C(n, n/2). This binomial coefficient can be estimated as ~2^n/(\pi * n/2) by large n. So, the complexity of the algo is O(2^n/(n)). However, if we also consider printing at end of recursion, we need to multiply with n, as it is the length of the outputted string. So, we end up with O(2^n)

To be clean, we need to prove that our assumption is correct. Hopefully you can do it by induction or other methods.

[UPDATE2]

Your implementation suffers from coping the string at each iteration. This slows down the execution by factor n. You can avoid it by passing a reference to the string and removing the added character after a recursive call like this:

void solve(string &op, int n, int zeros, int ones)
{
    if(n==0){
        cout<<op<<" ";
        return;
    }
    op.push_back('1');
    solve(op, n-1, zeros, ones+1);
    op.pop_back();
    if(ones > zeros){
        op.push_back('0');
        solve(op, n-1, zeros+1, ones);
        op.pop_back();
        return;
    }    
}

Upvotes: 4

Andy Wang
Andy Wang

Reputation: 1

If I understand you correctly, the time complexity for the function is O(N*2^N). I use the recursion tree to analyze the results.

Upvotes: 0

Related Questions