CODEWITHSUNDEEP
algorithmtime-complexitycombinations
Sheshang
Sheshang

Reputation: 83

Time Complexity Calculation for subsets generation function by k-sub algorithm

I have made one function which uses the k-sub algorithm (generating all subsets of size k from the set of n elements). and I am iterating over it for n times to create all subsets of all size (that is powerset).

Why am I using this function when I have already a method for generating powerset? Because I wanted subsets to be generated in increasing length of the subset.

for(int k = 0; k <= n; k++){
  recursiveSelectSubset(){
    if(k == n){
       for(int i = 0; i < n; i++){
               subset[i] = true;               
       }                
    }

    if(k == 0){
       for(int i = 0; i < n; i++){
               subset[i] = false;
       }
    }

    if(k > 0 && k < n){
       subset[n-1] = true;
       recursiveSelectSubset(subset, n-1, k-1, isminimum, io);
       subset[n-1] = false;
       recursiveSelectSubset(subset, n-1, k, isminimum, io);
    }                
  }
}

Now as the function is called n times, so n is there. but what is the complexity of recurciveSelectSubset function?

I felt like that function what does is generating all subsets of size k, so it is like nCk. which has complexity O(n^k). As now it runs for the all possible values for k from 1 to n we can say, final complexity for this snippet is O(n^(n+1))

This is how I calculated the complexity of recursiveSelectSubset. to generate all subsets of size k = 0, it will take n^0. To generate all subsets of size k = 1, it will take n^1. This way to generate subset of size k = n, it will take n^n. and total time will be n^0 + n^1 + .... + n^n = n^(n+1).

but here again doubt, to generate subset of size k = n, it should take constant time right? not n^n. So in that way my calculation goes wrong. but according to nCk, it can take n^n = n^0 = 1. So then how to total it for all values of k?

So what is the right complexity?

P.S. If my analysis is wrong, I would like to have clarification that how is it wrong?

Upvotes: 2

Views: 1263

Answers (1)

Sheshang
Sheshang

Reputation: 83

After some surfing and discussion, I found an answer, which I am posting here for the future help.

recursiveSelectSubset() will count nCk and takes time n^k. This function is being called for k = 0 to n.

So total time it takes is sum of the time taken by all calls to recurseiveSelectSubset().

n^0 + n^1 + n^2 + .... + n^n

This is actually the sum of binomial coefficients and it sums up to the 2^n. (here)

SO total time complexity for above function is 2^n.

Upvotes: 0

Related Questions