0
$\begingroup$

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a function $f$ to them and check something.

I understand that generating a power set is $O(2^n)$, but what complexity class does this belong to, and how do I prove it?

$\endgroup$
0
$\begingroup$

Complexity time $O(2^n)$ is called $DTIME(O(2^n))$ and is a sub-complexity class of E which is in turn a sub-complexity class of EXPTIME.

To prove you can do it within $O(2^n)$ time, you have to provide an algorithm for that and show the algorithm runs in no more than $O(2^n)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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