0
$\begingroup$

For Example let's say the given set is $\{1, 2, 3, 4\}$ i.e $n=4$ elements and I have to find the subsets possible till the maximum length of $k=2$.

To do this i've to do All possible combinations of subsets from length $0$ to length $k =2$ which causes time limit exceeded to my problem .

Since the calculation of total no of subsets i.e till the maximum length of set possible is much easier to find using $2^n$ which takes only $\log n$ time asymptotically

So my Question is.. Can we find this for $k$ in $\log(n)$ time which would be something like $2^n$ or in exponential form ?

$\endgroup$
5
  • $\begingroup$ Here's a MathJax tutorial :) $\endgroup$
    – Shaun
    Commented Oct 26, 2017 at 12:51
  • $\begingroup$ Are you looking for the number of subsets or do you wish to generate the subsets? If it's the latter, then for $k=n$ there are $2^n$ subsets. I don't see how these could be generated in less than $2^n$ operations. $\endgroup$
    – Jens
    Commented Oct 26, 2017 at 21:01
  • $\begingroup$ Yes i want the total number:) not the later $\endgroup$
    – Shailab Singh
    Commented Oct 27, 2017 at 0:08
  • $\begingroup$ The number of subsets is $$N = \sum_{i=0}^k \binom {n}{i}$$ Are you asking if there is a faster way to compute this than simply adding the $k$ terms? $\endgroup$
    – Jens
    Commented Oct 27, 2017 at 15:02
  • $\begingroup$ @Jens Yes i was asking that $\endgroup$
    – Shailab Singh
    Commented Nov 8, 2017 at 18:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .