0
$\begingroup$

I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like to know how to calculate the complexity of the algorithm. Can anyone help me with better clarification. Here is my code:

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
int N,M,a[15];
map<int,vector<int> >multiple;
void creating_subset(int i,int m,int l)
{
  if(i>=M)
  {
    multiple[l].push_back(m);
    return;
  }
  creating_subset(i+1,m*a[i],l+1);
  creating_subset(i+1,m,l);
}
int main()
{
  cin>>M;
  for(int i=0;i<M;i++)
  cin>>a[i];
  creating_subset(0,1,0);
  for(int i=0;i<multiple[3].size();i++)
  printf("%d ",multiple[3][i]);
  cout<<endl;
  return 0;
}
| cite | improve this question | |
$\endgroup$
  • 4
    $\begingroup$ A set of size $n$ has $2^n$ subsets, so enumerating them will take at least that many steps. For an upper bound, we'd have to know what your algorithm is. $\endgroup$ – Rick Decker Oct 13 '14 at 12:35
  • 1
    $\begingroup$ We can't help you unless you give us your algorithm and explain your data structures. They can slightly affect the complexity, but it is probably one of $O(2^n)$, $O(n2^n)$ or $O(n^22^n)$. $\endgroup$ – Yuval Filmus Oct 13 '14 at 13:03
  • $\begingroup$ You'll have to copy your code here and format it properly. Links may be gone, but this question stays and should be legible in the future. $\endgroup$ – Yuval Filmus Oct 13 '14 at 13:24
1
$\begingroup$

Your code doesn't really generate all subsets, but it does go over all subsets. The complexity of your code depends on the complexity of the data structures you use, which you'll have to figure out yourself. The proverbial "innermost loop" in your case is the if (i >= M), and this part runs $2^M$ times (once for each subset). If the complexity of the innermost loop is $C$, then the overall complexity of the code would be $O(2^M C)$, since the complexity of all other parts pales in comparison.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ how if(i>=M) parts run 2^M .please explain it again.what does c stand for? $\endgroup$ – awlad hossain Oct 13 '14 at 13:57
  • $\begingroup$ I haven't explained it, I stated it. Try tracing your program for small $M$ to see why it's true. $\endgroup$ – Yuval Filmus Oct 13 '14 at 13:59
  • $\begingroup$ ok,I have caught it why 2^M but why you have used C $\endgroup$ – awlad hossain Oct 13 '14 at 14:11
  • $\begingroup$ As I state, $C$ is the complexity (running time) of the innermost loop, or more accurately the amortized running time. Since it depends on the implementation details of the vector data structure, I cannot comment on that aspect of the code. $\endgroup$ – Yuval Filmus Oct 13 '14 at 14:13
  • $\begingroup$ For starters, you can assume for simplicity that $C = O(1)$, which sounds reasonable in this case, and so the overall complexity is $O(2^M)$. If, however, you were making a list of all subsets, $C$ would be $O(M)$ at the very least; indeed, the output length would be $O(M2^M)$. $\endgroup$ – Yuval Filmus Oct 13 '14 at 14:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.