Which of the following code have lesser time complexity? Please explain how to calculate it

Question

Following is the code to calculate subsets of a given array:

1. Bit Manipulation Method: How to analyse it?

    vector<vector<int>> subsets(vector<int>& nums)
     {
        sort(nums.begin(), nums.end());
   
        int num_subset = pow(2, nums.size()); 
        vector<vector<int> > res(num_subset, vector<int>());
   
        for (int i = 0; i < nums.size(); i++)
            for (int j = 0; j < num_subset; j++)
                if ((j >> i) & 1)
                    res[j].push_back(nums[i]);
   
        return res;  
     }
   

2. Backtracking Method: How to analyse it

        vector<vector<int>> subsets(vector<int>& nums)
         {
           sort(nums.begin(), nums.end()); // sort the original array
           vector<vector<int>> subs;
           vector<int> sub;  
           genSubsets(nums, 0, sub, subs);
           return subs; 
         }
   
       void genSubsets(vector<int>& nums, int start, vector<int>& sub,vector<vector<int>>& subs)
         {
           subs.push_back(sub);
           for (int i = start; i < nums.size(); i++) {
            sub.push_back(nums[i]);
            genSubsets(nums, i + 1, sub, subs);
            sub.pop_back();
          }
        }
   

Answer 1

Vector operations: - push_back and pop_back are both O(1) - Constructor with size argument n is O(n)

---

Bit manipulation method:

• sort is O(n log n)
• Construction of res is O(nums_subset) = O(2^n)

• Outer loop is executed n times, inner by nums_subset = 2^n times.

  

---

Backtracking method:

• Again, sort is O(n log n)

• Each genSubsets call loops through nums.size() - start times, each time performing a recursive call with 1 less loop.

  

---

Which is bigger? By Stirling's approximation,

So Backtracking is more costly.