6
$\begingroup$

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.


The original algorithm posted had a major flaw in its working. I tried my best but could not get the desired accuracy in presenting the algorithm in pseudo code and/or Set Theory notation. I am thus posting python code, which has been tested and produces the desired results.

Note that my question, however, remains the same: What is the time complexity of the algorithm (assuming that powersets are already generated)?

# mps is a set of powersets; below is a sample (test case)
mps = [
        [       [], [1], [2], [1,2]     ],
        [       [], [3], [4], [3,4]     ],
        [       [], [5], [6], [5,6]     ]
      ]


# Core algorithm
# enumerate(mps) may not be required in languages like C which support indexed loops
len = mps.__len__()
for idx, ps in enumerate(mps):
    if idx > len - 2:
            break;
    mps[idx + 1] = merge(mps[idx], mps[idx+1])   # merge is defined below


# Takes two powersets and merges them
def merge (psa, psb):
    fs = []
    for a in psa:
            for b in psb:
                    fs.append(list(set(a) | set(b)))
    return fs

Output: mps[-1] #Last item of the list

Running the above example will result in listing out the powerset of $\{1,2,3,4,5,6\}$.

$\endgroup$
6
  • $\begingroup$ I might not understand exactly what your F is. If you append sets to F, then F must be a list of sets, not necessarily unique ones. $\endgroup$ Aug 22 '12 at 15:03
  • $\begingroup$ @DavidToth As I mentioned in the edit to the question, the algorithm has a major flaw and I am posting the correction shortly. I hope that will lend further clarity. $\endgroup$ Aug 22 '12 at 15:05
  • $\begingroup$ @DavidToth Updated the algorithm. $\endgroup$ Aug 22 '12 at 15:19
  • $\begingroup$ Thank you for the update. I just wonder what is 'len' in 'if idx > len - 2'. $\endgroup$ Aug 22 '12 at 15:36
  • $\begingroup$ @DavidToth Thanks! len is the number of powersets in mps. Thus, 3 in our case. $\endgroup$ Aug 22 '12 at 15:39
2
$\begingroup$

EDIT: Since your new algorithm is slightly different, I present a new complexity analysis. I change the notation slightly of power-sets $P_a$ and $P_b$ to $P_1$ and $P_2$. Your algorithm generates a power-set $P = P(S_1 \cup S_2 \cup \cdots \cup S_n)$ where $P(S_i)=P_i$ given the power-sets $P_1, P_2, ..., P_n$.
In the body of the loop it performs the merge of two subsets $P_1$ and $P_2$.

What is the complexity of $\mathtt{merge}(P_1, P_2)$?

Define $|a|=\mathtt{len}(a)$ for a list $a$. The complexity of $\mathtt{set}(a) \mid \mathtt{set}(b)$ is $\mathcal{O}(|a|+|b|)$ according to Python Wiki for the union of two sets. The conversion $\mathtt{list}(\mathtt{set}(a) \mid \mathtt{set}(b))$ is asymptotically not worse than $\mathcal{O}(|a|+|b|)$, I guess it is either linear or sublinear depending how python implements it. Appending is constant, but since you are appending the whole list it is linear in terms of one list element as the whole list object will need to be copied in the memory, again $\mathcal{O}(|a|+|b|)$ . Thus the complexity of the loop body in a merge function is at most $\mathcal{O}(3(|a|+|b|)$ which is asymptotically equivalent to $\mathcal{O}(|a|+|b|)$.

The loop body in a merge function will be executed $|P_1||P_2|$ times. Thus the overall complexity of the merge function is $\mathcal{O}(|P_1||P_2|(|a|+|b|))$. Notice $a$, $b$ are elements of power-sets. Thus their lengths follow a binomial distribution. Therefore on average $|a|=0.5\log_2(|P_1|)$ and $|b|=0.5\log_2(|P_2|)$. This gives us

\begin{align} \mathcal{O}(|P_1||P_2|(|a|+|b|))&=\mathcal{O}(|P_1||P_2|(0.5\log_2(|P_1|)+0.5\log_2(|P_2|))\\ &=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1|)+\log_2(|P_2|))\\ &=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1||P_2|))\\ &=\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|)) \end{align} for the complexity of a merge algorithm for two power-sets $P_1$ and $P_2$.

Notice that the merge of $P_i$ and $P_{i+1}$ replaces $P_{i+1}$ for a power-set $\mathtt{merge}(P_{i}$,$P_{i+1})$ which is of length $2^{\log_2|P_i|+\log_2|P_{i+1}|}=|P_i||P_{i+1}|$.

After the first the first execution of the loop body in the main algorithm you will have executed $\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|))$ steps. $P_2$ has changed to $P_2'$ with the length $|P_1||P_2|$. After the second execution you will get another $\mathcal{O}(|P_2'||P_3|\log_2(|P_2'||P_3|))$ steps which is $\mathcal{O}(|P_1||P_2||P_3|\log_2(|P_1||P_2||P_3|))$ And then by the induction you finally get the complexity of the last step of the loop \begin{align} \mathcal{O}(|P_1||P_2|\cdots|P_n|\log_2(|P_1||P_2|\cdots|P_n|))&=\mathcal{O}(\Pi_{i=1}^n|P_i|\log_2(\Pi_{i=1}^n|P_i|))\\ &=\mathcal{O}(\Pi_{i=1}^n|P_i|\Sigma_{i=1}^n\log_2|P_i|). \end{align}

The complexity of the whole program is the sum of these complexities.

$\endgroup$
7
  • $\begingroup$ If you assume (dynamic) sorted arrays, the union can be computed with $2 \times (|M|+|N|-1)$ comparisons. The append runs in amortized constant time, but since $K$ is a set, the operation technically runs in time linear in the size of $K$, with $K \leq |S_a \cup S_b|$. $\endgroup$
    – Juho
    Aug 21 '12 at 16:28
  • $\begingroup$ Yes, you are right. But whatever complexity time (constant, linear, polynomial) it takes for the inner loop operations, if less than exponential, it will eventually get simplified to the final expression O(2^(sa+sb)). $\endgroup$ Aug 21 '12 at 17:08
  • $\begingroup$ @DavidToth I think the reason that you are getting an exponential running time is because you are considering generation of $\mathcal P \left({S}\right)$ itself as a part of the algorithm. But note that it has been given as an input, therefore one need not compute the power set itself as a part of the algorithm. What you take as $s_a$ is not a set of elements but the power set itself. Am I right? $\endgroup$ Aug 22 '12 at 2:19
  • $\begingroup$ @DavidToth On seconds thoughts, I see that you present the complexity in terms of the number of elements in the base set. But, should we not consider the complexity of the algorithm based on the input, which in this case is the powerset itself. $\endgroup$ Aug 22 '12 at 2:21
  • $\begingroup$ @WeaklyTyped Yes, if we considered the complexity based on the input, then the running time would not be exponential. But then the input sets do now have to be power-sets, it would be true for any sets. The resulting complexity would be O(|Pa|*|Pb|*alpha). Now I see your point, the lengths of subsets of power-sets follow a certain distribution. I'll post workings later. $\endgroup$ Aug 22 '12 at 5:11

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.